lib/librte_hash/rte_cuckoo_hash.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2010-2016 Intel Corporation
   3  */
   4
   5 #include <string.h>
   6 #include <stdint.h>
   7 #include <errno.h>
   8 #include <stdio.h>
   9 #include <stdarg.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_memcpy.h>
  16 #include <rte_prefetch.h>
  17 #include <rte_branch_prediction.h>
  18 #include <rte_malloc.h>
  19 #include <rte_eal.h>
  20 #include <rte_eal_memconfig.h>
  21 #include <rte_per_lcore.h>
  22 #include <rte_errno.h>
  23 #include <rte_string_fns.h>
  24 #include <rte_cpuflags.h>
  25 #include <rte_rwlock.h>
  26 #include <rte_spinlock.h>
  27 #include <rte_ring.h>
  28 #include <rte_compat.h>
  29 #include <rte_pause.h>
  30
  31 #include "rte_hash.h"
  32 #include "rte_cuckoo_hash.h"
  33
  34 #define FOR_EACH_BUCKET(CURRENT_BKT, START_BUCKET)                            \
  35         for (CURRENT_BKT = START_BUCKET;                                      \
  36                 CURRENT_BKT != NULL;                                          \
  37                 CURRENT_BKT = CURRENT_BKT->next)
  38
  39 TAILQ_HEAD(rte_hash_list, rte_tailq_entry);
  40
  41 static struct rte_tailq_elem rte_hash_tailq = {
  42         .name = "RTE_HASH",
  43 };
  44 EAL_REGISTER_TAILQ(rte_hash_tailq)
  45
  46 struct rte_hash *
  47 rte_hash_find_existing(const char *name)
  48 {
  49         struct rte_hash *h = NULL;
  50         struct rte_tailq_entry *te;
  51         struct rte_hash_list *hash_list;
  52
  53         hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
  54
  55         rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
  56         TAILQ_FOREACH(te, hash_list, next) {
  57                 h = (struct rte_hash *) te->data;
  58                 if (strncmp(name, h->name, RTE_HASH_NAMESIZE) == 0)
  59                         break;
  60         }
  61         rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
  62
  63         if (te == NULL) {
  64                 rte_errno = ENOENT;
  65                 return NULL;
  66         }
  67         return h;
  68 }
  69
  70 static inline struct rte_hash_bucket *
  71 rte_hash_get_last_bkt(struct rte_hash_bucket *lst_bkt)
  72 {
  73         while (lst_bkt->next != NULL)
  74                 lst_bkt = lst_bkt->next;
  75         return lst_bkt;
  76 }
  77
  78 void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t func)
  79 {
  80         h->cmp_jump_table_idx = KEY_CUSTOM;
  81         h->rte_hash_custom_cmp_eq = func;
  82 }
  83
  84 static inline int
  85 rte_hash_cmp_eq(const void *key1, const void *key2, const struct rte_hash *h)
  86 {
  87         if (h->cmp_jump_table_idx == KEY_CUSTOM)
  88                 return h->rte_hash_custom_cmp_eq(key1, key2, h->key_len);
  89         else
  90                 return cmp_jump_table[h->cmp_jump_table_idx](key1, key2, h->key_len);
  91 }
  92
  93 /*
  94  * We use higher 16 bits of hash as the signature value stored in table.
  95  * We use the lower bits for the primary bucket
  96  * location. Then we XOR primary bucket location and the signature
  97  * to get the secondary bucket location. This is same as
  98  * proposed in Bin Fan, et al's paper
  99  * "MemC3: Compact and Concurrent MemCache with Dumber Caching and
 100  * Smarter Hashing". The benefit to use
 101  * XOR is that one could derive the alternative bucket location
 102  * by only using the current bucket location and the signature.
 103  */
 104 static inline uint16_t
 105 get_short_sig(const hash_sig_t hash)
 106 {
 107         return hash >> 16;
 108 }
 109
 110 static inline uint32_t
 111 get_prim_bucket_index(const struct rte_hash *h, const hash_sig_t hash)
 112 {
 113         return hash & h->bucket_bitmask;
 114 }
 115
 116 static inline uint32_t
 117 get_alt_bucket_index(const struct rte_hash *h,
 118                         uint32_t cur_bkt_idx, uint16_t sig)
 119 {
 120         return (cur_bkt_idx ^ sig) & h->bucket_bitmask;
 121 }
 122
 123 struct rte_hash *
 124 rte_hash_create(const struct rte_hash_parameters *params)
 125 {
 126         struct rte_hash *h = NULL;
 127         struct rte_tailq_entry *te = NULL;
 128         struct rte_hash_list *hash_list;
 129         struct rte_ring *r = NULL;
 130         struct rte_ring *r_ext = NULL;
 131         char hash_name[RTE_HASH_NAMESIZE];
 132         void *k = NULL;
 133         void *buckets = NULL;
 134         void *buckets_ext = NULL;
 135         char ring_name[RTE_RING_NAMESIZE];
 136         char ext_ring_name[RTE_RING_NAMESIZE];
 137         unsigned num_key_slots;
 138         unsigned i;
 139         unsigned int hw_trans_mem_support = 0, multi_writer_support = 0;
 140         unsigned int ext_table_support = 0;
 141         unsigned int readwrite_concur_support = 0;
 142
 143         rte_hash_function default_hash_func = (rte_hash_function)rte_jhash;
 144
 145         hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
 146
 147         if (params == NULL) {
 148                 RTE_LOG(ERR, HASH, "rte_hash_create has no parameters\n");
 149                 return NULL;
 150         }
 151
 152         /* Check for valid parameters */
 153         if ((params->entries > RTE_HASH_ENTRIES_MAX) ||
 154                         (params->entries < RTE_HASH_BUCKET_ENTRIES) ||
 155                         (params->key_len == 0)) {
 156                 rte_errno = EINVAL;
 157                 RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n");
 158                 return NULL;
 159         }
 160
 161         /* Check extra flags field to check extra options. */
 162         if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT)
 163                 hw_trans_mem_support = 1;
 164
 165         if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD)
 166                 multi_writer_support = 1;
 167
 168         if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY) {
 169                 readwrite_concur_support = 1;
 170                 multi_writer_support = 1;
 171         }
 172
 173         if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE)
 174                 ext_table_support = 1;
 175
 176         /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */
 177         if (multi_writer_support)
 178                 /*
 179                  * Increase number of slots by total number of indices
 180                  * that can be stored in the lcore caches
 181                  * except for the first cache
 182                  */
 183                 num_key_slots = params->entries + (RTE_MAX_LCORE - 1) *
 184                                         (LCORE_CACHE_SIZE - 1) + 1;
 185         else
 186                 num_key_slots = params->entries + 1;
 187
 188         snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name);
 189         /* Create ring (Dummy slot index is not enqueued) */
 190         r = rte_ring_create(ring_name, rte_align32pow2(num_key_slots),
 191                         params->socket_id, 0);
 192         if (r == NULL) {
 193                 RTE_LOG(ERR, HASH, "memory allocation failed\n");
 194                 goto err;
 195         }
 196
 197         const uint32_t num_buckets = rte_align32pow2(params->entries) /
 198                                                 RTE_HASH_BUCKET_ENTRIES;
 199
 200         /* Create ring for extendable buckets. */
 201         if (ext_table_support) {
 202                 snprintf(ext_ring_name, sizeof(ext_ring_name), "HT_EXT_%s",
 203                                                                 params->name);
 204                 r_ext = rte_ring_create(ext_ring_name,
 205                                 rte_align32pow2(num_buckets + 1),
 206                                 params->socket_id, 0);
 207
 208                 if (r_ext == NULL) {
 209                         RTE_LOG(ERR, HASH, "ext buckets memory allocation "
 210                                                                 "failed\n");
 211                         goto err;
 212                 }
 213         }
 214
 215         snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name);
 216
 217         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
 218
 219         /* guarantee there's no existing: this is normally already checked
 220          * by ring creation above */
 221         TAILQ_FOREACH(te, hash_list, next) {
 222                 h = (struct rte_hash *) te->data;
 223                 if (strncmp(params->name, h->name, RTE_HASH_NAMESIZE) == 0)
 224                         break;
 225         }
 226         h = NULL;
 227         if (te != NULL) {
 228                 rte_errno = EEXIST;
 229                 te = NULL;
 230                 goto err_unlock;
 231         }
 232
 233         te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0);
 234         if (te == NULL) {
 235                 RTE_LOG(ERR, HASH, "tailq entry allocation failed\n");
 236                 goto err_unlock;
 237         }
 238
 239         h = (struct rte_hash *)rte_zmalloc_socket(hash_name, sizeof(struct rte_hash),
 240                                         RTE_CACHE_LINE_SIZE, params->socket_id);
 241
 242         if (h == NULL) {
 243                 RTE_LOG(ERR, HASH, "memory allocation failed\n");
 244                 goto err_unlock;
 245         }
 246
 247         buckets = rte_zmalloc_socket(NULL,
 248                                 num_buckets * sizeof(struct rte_hash_bucket),
 249                                 RTE_CACHE_LINE_SIZE, params->socket_id);
 250
 251         if (buckets == NULL) {
 252                 RTE_LOG(ERR, HASH, "buckets memory allocation failed\n");
 253                 goto err_unlock;
 254         }
 255
 256         /* Allocate same number of extendable buckets */
 257         if (ext_table_support) {
 258                 buckets_ext = rte_zmalloc_socket(NULL,
 259                                 num_buckets * sizeof(struct rte_hash_bucket),
 260                                 RTE_CACHE_LINE_SIZE, params->socket_id);
 261                 if (buckets_ext == NULL) {
 262                         RTE_LOG(ERR, HASH, "ext buckets memory allocation "
 263                                                         "failed\n");
 264                         goto err_unlock;
 265                 }
 266                 /* Populate ext bkt ring. We reserve 0 similar to the
 267                  * key-data slot, just in case in future we want to
 268                  * use bucket index for the linked list and 0 means NULL
 269                  * for next bucket
 270                  */
 271                 for (i = 1; i <= num_buckets; i++)
 272                         rte_ring_sp_enqueue(r_ext, (void *)((uintptr_t) i));
 273         }
 274
 275         const uint32_t key_entry_size = sizeof(struct rte_hash_key) + params->key_len;
 276         const uint64_t key_tbl_size = (uint64_t) key_entry_size * num_key_slots;
 277
 278         k = rte_zmalloc_socket(NULL, key_tbl_size,
 279                         RTE_CACHE_LINE_SIZE, params->socket_id);
 280
 281         if (k == NULL) {
 282                 RTE_LOG(ERR, HASH, "memory allocation failed\n");
 283                 goto err_unlock;
 284         }
 285
 286 /*
 287  * If x86 architecture is used, select appropriate compare function,
 288  * which may use x86 intrinsics, otherwise use memcmp
 289  */
 290 #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
 291         /* Select function to compare keys */
 292         switch (params->key_len) {
 293         case 16:
 294                 h->cmp_jump_table_idx = KEY_16_BYTES;
 295                 break;
 296         case 32:
 297                 h->cmp_jump_table_idx = KEY_32_BYTES;
 298                 break;
 299         case 48:
 300                 h->cmp_jump_table_idx = KEY_48_BYTES;
 301                 break;
 302         case 64:
 303                 h->cmp_jump_table_idx = KEY_64_BYTES;
 304                 break;
 305         case 80:
 306                 h->cmp_jump_table_idx = KEY_80_BYTES;
 307                 break;
 308         case 96:
 309                 h->cmp_jump_table_idx = KEY_96_BYTES;
 310                 break;
 311         case 112:
 312                 h->cmp_jump_table_idx = KEY_112_BYTES;
 313                 break;
 314         case 128:
 315                 h->cmp_jump_table_idx = KEY_128_BYTES;
 316                 break;
 317         default:
 318                 /* If key is not multiple of 16, use generic memcmp */
 319                 h->cmp_jump_table_idx = KEY_OTHER_BYTES;
 320         }
 321 #else
 322         h->cmp_jump_table_idx = KEY_OTHER_BYTES;
 323 #endif
 324
 325         if (multi_writer_support) {
 326                 h->local_free_slots = rte_zmalloc_socket(NULL,
 327                                 sizeof(struct lcore_cache) * RTE_MAX_LCORE,
 328                                 RTE_CACHE_LINE_SIZE, params->socket_id);
 329         }
 330
 331         /* Default hash function */
 332 #if defined(RTE_ARCH_X86)
 333         default_hash_func = (rte_hash_function)rte_hash_crc;
 334 #elif defined(RTE_ARCH_ARM64)
 335         if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_CRC32))
 336                 default_hash_func = (rte_hash_function)rte_hash_crc;
 337 #endif
 338         /* Setup hash context */
 339         snprintf(h->name, sizeof(h->name), "%s", params->name);
 340         h->entries = params->entries;
 341         h->key_len = params->key_len;
 342         h->key_entry_size = key_entry_size;
 343         h->hash_func_init_val = params->hash_func_init_val;
 344
 345         h->num_buckets = num_buckets;
 346         h->bucket_bitmask = h->num_buckets - 1;
 347         h->buckets = buckets;
 348         h->buckets_ext = buckets_ext;
 349         h->free_ext_bkts = r_ext;
 350         h->hash_func = (params->hash_func == NULL) ?
 351                 default_hash_func : params->hash_func;
 352         h->key_store = k;
 353         h->free_slots = r;
 354         h->hw_trans_mem_support = hw_trans_mem_support;
 355         h->multi_writer_support = multi_writer_support;
 356         h->readwrite_concur_support = readwrite_concur_support;
 357         h->ext_table_support = ext_table_support;
 358
 359 #if defined(RTE_ARCH_X86)
 360         if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SSE2))
 361                 h->sig_cmp_fn = RTE_HASH_COMPARE_SSE;
 362         else
 363 #endif
 364                 h->sig_cmp_fn = RTE_HASH_COMPARE_SCALAR;
 365
 366         /* Turn on multi-writer only with explicit flag from user and TM
 367          * support.
 368          */
 369         if (h->multi_writer_support) {
 370                 h->readwrite_lock = rte_malloc(NULL, sizeof(rte_rwlock_t),
 371                                                 RTE_CACHE_LINE_SIZE);
 372                 if (h->readwrite_lock == NULL)
 373                         goto err_unlock;
 374
 375                 rte_rwlock_init(h->readwrite_lock);
 376         }
 377
 378         /* Populate free slots ring. Entry zero is reserved for key misses. */
 379         for (i = 1; i < num_key_slots; i++)
 380                 rte_ring_sp_enqueue(r, (void *)((uintptr_t) i));
 381
 382         te->data = (void *) h;
 383         TAILQ_INSERT_TAIL(hash_list, te, next);
 384         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 385
 386         return h;
 387 err_unlock:
 388         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 389 err:
 390         rte_ring_free(r);
 391         rte_ring_free(r_ext);
 392         rte_free(te);
 393         rte_free(h);
 394         rte_free(buckets);
 395         rte_free(buckets_ext);
 396         rte_free(k);
 397         return NULL;
 398 }
 399
 400 void
 401 rte_hash_free(struct rte_hash *h)
 402 {
 403         struct rte_tailq_entry *te;
 404         struct rte_hash_list *hash_list;
 405
 406         if (h == NULL)
 407                 return;
 408
 409         hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
 410
 411         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
 412
 413         /* find out tailq entry */
 414         TAILQ_FOREACH(te, hash_list, next) {
 415                 if (te->data == (void *) h)
 416                         break;
 417         }
 418
 419         if (te == NULL) {
 420                 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 421                 return;
 422         }
 423
 424         TAILQ_REMOVE(hash_list, te, next);
 425
 426         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 427
 428         if (h->multi_writer_support) {
 429                 rte_free(h->local_free_slots);
 430                 rte_free(h->readwrite_lock);
 431         }
 432         rte_ring_free(h->free_slots);
 433         rte_ring_free(h->free_ext_bkts);
 434         rte_free(h->key_store);
 435         rte_free(h->buckets);
 436         rte_free(h->buckets_ext);
 437         rte_free(h);
 438         rte_free(te);
 439 }
 440
 441 hash_sig_t
 442 rte_hash_hash(const struct rte_hash *h, const void *key)
 443 {
 444         /* calc hash result by key */
 445         return h->hash_func(key, h->key_len, h->hash_func_init_val);
 446 }
 447
 448 int32_t
 449 rte_hash_count(const struct rte_hash *h)
 450 {
 451         uint32_t tot_ring_cnt, cached_cnt = 0;
 452         uint32_t i, ret;
 453
 454         if (h == NULL)
 455                 return -EINVAL;
 456
 457         if (h->multi_writer_support) {
 458                 tot_ring_cnt = h->entries + (RTE_MAX_LCORE - 1) *
 459                                         (LCORE_CACHE_SIZE - 1);
 460                 for (i = 0; i < RTE_MAX_LCORE; i++)
 461                         cached_cnt += h->local_free_slots[i].len;
 462
 463                 ret = tot_ring_cnt - rte_ring_count(h->free_slots) -
 464                                                                 cached_cnt;
 465         } else {
 466                 tot_ring_cnt = h->entries;
 467                 ret = tot_ring_cnt - rte_ring_count(h->free_slots);
 468         }
 469         return ret;
 470 }
 471
 472 /* Read write locks implemented using rte_rwlock */
 473 static inline void
 474 __hash_rw_writer_lock(const struct rte_hash *h)
 475 {
 476         if (h->multi_writer_support && h->hw_trans_mem_support)
 477                 rte_rwlock_write_lock_tm(h->readwrite_lock);
 478         else if (h->multi_writer_support)
 479                 rte_rwlock_write_lock(h->readwrite_lock);
 480 }
 481
 482 static inline void
 483 __hash_rw_reader_lock(const struct rte_hash *h)
 484 {
 485         if (h->readwrite_concur_support && h->hw_trans_mem_support)
 486                 rte_rwlock_read_lock_tm(h->readwrite_lock);
 487         else if (h->readwrite_concur_support)
 488                 rte_rwlock_read_lock(h->readwrite_lock);
 489 }
 490
 491 static inline void
 492 __hash_rw_writer_unlock(const struct rte_hash *h)
 493 {
 494         if (h->multi_writer_support && h->hw_trans_mem_support)
 495                 rte_rwlock_write_unlock_tm(h->readwrite_lock);
 496         else if (h->multi_writer_support)
 497                 rte_rwlock_write_unlock(h->readwrite_lock);
 498 }
 499
 500 static inline void
 501 __hash_rw_reader_unlock(const struct rte_hash *h)
 502 {
 503         if (h->readwrite_concur_support && h->hw_trans_mem_support)
 504                 rte_rwlock_read_unlock_tm(h->readwrite_lock);
 505         else if (h->readwrite_concur_support)
 506                 rte_rwlock_read_unlock(h->readwrite_lock);
 507 }
 508
 509 void
 510 rte_hash_reset(struct rte_hash *h)
 511 {
 512         void *ptr;
 513         uint32_t tot_ring_cnt, i;
 514
 515         if (h == NULL)
 516                 return;
 517
 518         __hash_rw_writer_lock(h);
 519         memset(h->buckets, 0, h->num_buckets * sizeof(struct rte_hash_bucket));
 520         memset(h->key_store, 0, h->key_entry_size * (h->entries + 1));
 521
 522         /* clear the free ring */
 523         while (rte_ring_dequeue(h->free_slots, &ptr) == 0)
 524                 rte_pause();
 525
 526         /* clear free extendable bucket ring and memory */
 527         if (h->ext_table_support) {
 528                 memset(h->buckets_ext, 0, h->num_buckets *
 529                                                 sizeof(struct rte_hash_bucket));
 530                 while (rte_ring_dequeue(h->free_ext_bkts, &ptr) == 0)
 531                         rte_pause();
 532         }
 533
 534         /* Repopulate the free slots ring. Entry zero is reserved for key misses */
 535         if (h->multi_writer_support)
 536                 tot_ring_cnt = h->entries + (RTE_MAX_LCORE - 1) *
 537                                         (LCORE_CACHE_SIZE - 1);
 538         else
 539                 tot_ring_cnt = h->entries;
 540
 541         for (i = 1; i < tot_ring_cnt + 1; i++)
 542                 rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t) i));
 543
 544         /* Repopulate the free ext bkt ring. */
 545         if (h->ext_table_support) {
 546                 for (i = 1; i <= h->num_buckets; i++)
 547                         rte_ring_sp_enqueue(h->free_ext_bkts,
 548                                                 (void *)((uintptr_t) i));
 549         }
 550
 551         if (h->multi_writer_support) {
 552                 /* Reset local caches per lcore */
 553                 for (i = 0; i < RTE_MAX_LCORE; i++)
 554                         h->local_free_slots[i].len = 0;
 555         }
 556         __hash_rw_writer_unlock(h);
 557 }
 558
 559 /*
 560  * Function called to enqueue back an index in the cache/ring,
 561  * as slot has not being used and it can be used in the
 562  * next addition attempt.
 563  */
 564 static inline void
 565 enqueue_slot_back(const struct rte_hash *h,
 566                 struct lcore_cache *cached_free_slots,
 567                 void *slot_id)
 568 {
 569         if (h->multi_writer_support) {
 570                 cached_free_slots->objs[cached_free_slots->len] = slot_id;
 571                 cached_free_slots->len++;
 572         } else
 573                 rte_ring_sp_enqueue(h->free_slots, slot_id);
 574 }
 575
 576 /* Search a key from bucket and update its data */
 577 static inline int32_t
 578 search_and_update(const struct rte_hash *h, void *data, const void *key,
 579         struct rte_hash_bucket *bkt, uint16_t sig)
 580 {
 581         int i;
 582         struct rte_hash_key *k, *keys = h->key_store;
 583
 584         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 585                 if (bkt->sig_current[i] == sig) {
 586                         k = (struct rte_hash_key *) ((char *)keys +
 587                                         bkt->key_idx[i] * h->key_entry_size);
 588                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
 589                                 /* Update data */
 590                                 k->pdata = data;
 591                                 /*
 592                                  * Return index where key is stored,
 593                                  * subtracting the first dummy index
 594                                  */
 595                                 return bkt->key_idx[i] - 1;
 596                         }
 597                 }
 598         }
 599         return -1;
 600 }
 601
 602 /* Only tries to insert at one bucket (@prim_bkt) without trying to push
 603  * buckets around.
 604  * return 1 if matching existing key, return 0 if succeeds, return -1 for no
 605  * empty entry.
 606  */
 607 static inline int32_t
 608 rte_hash_cuckoo_insert_mw(const struct rte_hash *h,
 609                 struct rte_hash_bucket *prim_bkt,
 610                 struct rte_hash_bucket *sec_bkt,
 611                 const struct rte_hash_key *key, void *data,
 612                 uint16_t sig, uint32_t new_idx,
 613                 int32_t *ret_val)
 614 {
 615         unsigned int i;
 616         struct rte_hash_bucket *cur_bkt;
 617         int32_t ret;
 618
 619         __hash_rw_writer_lock(h);
 620         /* Check if key was inserted after last check but before this
 621          * protected region in case of inserting duplicated keys.
 622          */
 623         ret = search_and_update(h, data, key, prim_bkt, sig);
 624         if (ret != -1) {
 625                 __hash_rw_writer_unlock(h);
 626                 *ret_val = ret;
 627                 return 1;
 628         }
 629
 630         FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
 631                 ret = search_and_update(h, data, key, cur_bkt, sig);
 632                 if (ret != -1) {
 633                         __hash_rw_writer_unlock(h);
 634                         *ret_val = ret;
 635                         return 1;
 636                 }
 637         }
 638
 639         /* Insert new entry if there is room in the primary
 640          * bucket.
 641          */
 642         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 643                 /* Check if slot is available */
 644                 if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) {
 645                         prim_bkt->sig_current[i] = sig;
 646                         prim_bkt->key_idx[i] = new_idx;
 647                         break;
 648                 }
 649         }
 650         __hash_rw_writer_unlock(h);
 651
 652         if (i != RTE_HASH_BUCKET_ENTRIES)
 653                 return 0;
 654
 655         /* no empty entry */
 656         return -1;
 657 }
 658
 659 /* Shift buckets along provided cuckoo_path (@leaf and @leaf_slot) and fill
 660  * the path head with new entry (sig, alt_hash, new_idx)
 661  * return 1 if matched key found, return -1 if cuckoo path invalided and fail,
 662  * return 0 if succeeds.
 663  */
 664 static inline int
 665 rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,
 666                         struct rte_hash_bucket *bkt,
 667                         struct rte_hash_bucket *alt_bkt,
 668                         const struct rte_hash_key *key, void *data,
 669                         struct queue_node *leaf, uint32_t leaf_slot,
 670                         uint16_t sig, uint32_t new_idx,
 671                         int32_t *ret_val)
 672 {
 673         uint32_t prev_alt_bkt_idx;
 674         struct rte_hash_bucket *cur_bkt;
 675         struct queue_node *prev_node, *curr_node = leaf;
 676         struct rte_hash_bucket *prev_bkt, *curr_bkt = leaf->bkt;
 677         uint32_t prev_slot, curr_slot = leaf_slot;
 678         int32_t ret;
 679
 680         __hash_rw_writer_lock(h);
 681
 682         /* In case empty slot was gone before entering protected region */
 683         if (curr_bkt->key_idx[curr_slot] != EMPTY_SLOT) {
 684                 __hash_rw_writer_unlock(h);
 685                 return -1;
 686         }
 687
 688         /* Check if key was inserted after last check but before this
 689          * protected region.
 690          */
 691         ret = search_and_update(h, data, key, bkt, sig);
 692         if (ret != -1) {
 693                 __hash_rw_writer_unlock(h);
 694                 *ret_val = ret;
 695                 return 1;
 696         }
 697
 698         FOR_EACH_BUCKET(cur_bkt, alt_bkt) {
 699                 ret = search_and_update(h, data, key, cur_bkt, sig);
 700                 if (ret != -1) {
 701                         __hash_rw_writer_unlock(h);
 702                         *ret_val = ret;
 703                         return 1;
 704                 }
 705         }
 706
 707         while (likely(curr_node->prev != NULL)) {
 708                 prev_node = curr_node->prev;
 709                 prev_bkt = prev_node->bkt;
 710                 prev_slot = curr_node->prev_slot;
 711
 712                 prev_alt_bkt_idx = get_alt_bucket_index(h,
 713                                         prev_node->cur_bkt_idx,
 714                                         prev_bkt->sig_current[prev_slot]);
 715
 716                 if (unlikely(&h->buckets[prev_alt_bkt_idx]
 717                                 != curr_bkt)) {
 718                         /* revert it to empty, otherwise duplicated keys */
 719                         curr_bkt->key_idx[curr_slot] = EMPTY_SLOT;
 720                         __hash_rw_writer_unlock(h);
 721                         return -1;
 722                 }
 723
 724                 /* Need to swap current/alt sig to allow later
 725                  * Cuckoo insert to move elements back to its
 726                  * primary bucket if available
 727                  */
 728                 curr_bkt->sig_current[curr_slot] =
 729                         prev_bkt->sig_current[prev_slot];
 730                 curr_bkt->key_idx[curr_slot] =
 731                         prev_bkt->key_idx[prev_slot];
 732
 733                 curr_slot = prev_slot;
 734                 curr_node = prev_node;
 735                 curr_bkt = curr_node->bkt;
 736         }
 737
 738         curr_bkt->sig_current[curr_slot] = sig;
 739         curr_bkt->key_idx[curr_slot] = new_idx;
 740
 741         __hash_rw_writer_unlock(h);
 742
 743         return 0;
 744
 745 }
 746
 747 /*
 748  * Make space for new key, using bfs Cuckoo Search and Multi-Writer safe
 749  * Cuckoo
 750  */
 751 static inline int
 752 rte_hash_cuckoo_make_space_mw(const struct rte_hash *h,
 753                         struct rte_hash_bucket *bkt,
 754                         struct rte_hash_bucket *sec_bkt,
 755                         const struct rte_hash_key *key, void *data,
 756                         uint16_t sig, uint32_t bucket_idx,
 757                         uint32_t new_idx, int32_t *ret_val)
 758 {
 759         unsigned int i;
 760         struct queue_node queue[RTE_HASH_BFS_QUEUE_MAX_LEN];
 761         struct queue_node *tail, *head;
 762         struct rte_hash_bucket *curr_bkt, *alt_bkt;
 763         uint32_t cur_idx, alt_idx;
 764
 765         tail = queue;
 766         head = queue + 1;
 767         tail->bkt = bkt;
 768         tail->prev = NULL;
 769         tail->prev_slot = -1;
 770         tail->cur_bkt_idx = bucket_idx;
 771
 772         /* Cuckoo bfs Search */
 773         while (likely(tail != head && head <
 774                                         queue + RTE_HASH_BFS_QUEUE_MAX_LEN -
 775                                         RTE_HASH_BUCKET_ENTRIES)) {
 776                 curr_bkt = tail->bkt;
 777                 cur_idx = tail->cur_bkt_idx;
 778                 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 779                         if (curr_bkt->key_idx[i] == EMPTY_SLOT) {
 780                                 int32_t ret = rte_hash_cuckoo_move_insert_mw(h,
 781                                                 bkt, sec_bkt, key, data,
 782                                                 tail, i, sig,
 783                                                 new_idx, ret_val);
 784                                 if (likely(ret != -1))
 785                                         return ret;
 786                         }
 787
 788                         /* Enqueue new node and keep prev node info */
 789                         alt_idx = get_alt_bucket_index(h, cur_idx,
 790                                                 curr_bkt->sig_current[i]);
 791                         alt_bkt = &(h->buckets[alt_idx]);
 792                         head->bkt = alt_bkt;
 793                         head->cur_bkt_idx = alt_idx;
 794                         head->prev = tail;
 795                         head->prev_slot = i;
 796                         head++;
 797                 }
 798                 tail++;
 799         }
 800
 801         return -ENOSPC;
 802 }
 803
 804 static inline int32_t
 805 __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
 806                                                 hash_sig_t sig, void *data)
 807 {
 808         uint16_t short_sig;
 809         uint32_t prim_bucket_idx, sec_bucket_idx;
 810         struct rte_hash_bucket *prim_bkt, *sec_bkt, *cur_bkt;
 811         struct rte_hash_key *new_k, *keys = h->key_store;
 812         void *slot_id = NULL;
 813         void *ext_bkt_id = NULL;
 814         uint32_t new_idx, bkt_id;
 815         int ret;
 816         unsigned n_slots;
 817         unsigned lcore_id;
 818         unsigned int i;
 819         struct lcore_cache *cached_free_slots = NULL;
 820         int32_t ret_val;
 821         struct rte_hash_bucket *last;
 822
 823         short_sig = get_short_sig(sig);
 824         prim_bucket_idx = get_prim_bucket_index(h, sig);
 825         sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig);
 826         prim_bkt = &h->buckets[prim_bucket_idx];
 827         sec_bkt = &h->buckets[sec_bucket_idx];
 828         rte_prefetch0(prim_bkt);
 829         rte_prefetch0(sec_bkt);
 830
 831         /* Check if key is already inserted in primary location */
 832         __hash_rw_writer_lock(h);
 833         ret = search_and_update(h, data, key, prim_bkt, short_sig);
 834         if (ret != -1) {
 835                 __hash_rw_writer_unlock(h);
 836                 return ret;
 837         }
 838
 839         /* Check if key is already inserted in secondary location */
 840         FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
 841                 ret = search_and_update(h, data, key, cur_bkt, short_sig);
 842                 if (ret != -1) {
 843                         __hash_rw_writer_unlock(h);
 844                         return ret;
 845                 }
 846         }
 847
 848         __hash_rw_writer_unlock(h);
 849
 850         /* Did not find a match, so get a new slot for storing the new key */
 851         if (h->multi_writer_support) {
 852                 lcore_id = rte_lcore_id();
 853                 cached_free_slots = &h->local_free_slots[lcore_id];
 854                 /* Try to get a free slot from the local cache */
 855                 if (cached_free_slots->len == 0) {
 856                         /* Need to get another burst of free slots from global ring */
 857                         n_slots = rte_ring_mc_dequeue_burst(h->free_slots,
 858                                         cached_free_slots->objs,
 859                                         LCORE_CACHE_SIZE, NULL);
 860                         if (n_slots == 0) {
 861                                 return -ENOSPC;
 862                         }
 863
 864                         cached_free_slots->len += n_slots;
 865                 }
 866
 867                 /* Get a free slot from the local cache */
 868                 cached_free_slots->len--;
 869                 slot_id = cached_free_slots->objs[cached_free_slots->len];
 870         } else {
 871                 if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0) {
 872                         return -ENOSPC;
 873                 }
 874         }
 875
 876         new_k = RTE_PTR_ADD(keys, (uintptr_t)slot_id * h->key_entry_size);
 877         new_idx = (uint32_t)((uintptr_t) slot_id);
 878         /* Copy key */
 879         rte_memcpy(new_k->key, key, h->key_len);
 880         new_k->pdata = data;
 881
 882
 883         /* Find an empty slot and insert */
 884         ret = rte_hash_cuckoo_insert_mw(h, prim_bkt, sec_bkt, key, data,
 885                                         short_sig, new_idx, &ret_val);
 886         if (ret == 0)
 887                 return new_idx - 1;
 888         else if (ret == 1) {
 889                 enqueue_slot_back(h, cached_free_slots, slot_id);
 890                 return ret_val;
 891         }
 892
 893         /* Primary bucket full, need to make space for new entry */
 894         ret = rte_hash_cuckoo_make_space_mw(h, prim_bkt, sec_bkt, key, data,
 895                                 short_sig, prim_bucket_idx, new_idx, &ret_val);
 896         if (ret == 0)
 897                 return new_idx - 1;
 898         else if (ret == 1) {
 899                 enqueue_slot_back(h, cached_free_slots, slot_id);
 900                 return ret_val;
 901         }
 902
 903         /* Also search secondary bucket to get better occupancy */
 904         ret = rte_hash_cuckoo_make_space_mw(h, sec_bkt, prim_bkt, key, data,
 905                                 short_sig, sec_bucket_idx, new_idx, &ret_val);
 906
 907         if (ret == 0)
 908                 return new_idx - 1;
 909         else if (ret == 1) {
 910                 enqueue_slot_back(h, cached_free_slots, slot_id);
 911                 return ret_val;
 912         }
 913
 914         /* if ext table not enabled, we failed the insertion */
 915         if (!h->ext_table_support) {
 916                 enqueue_slot_back(h, cached_free_slots, slot_id);
 917                 return ret;
 918         }
 919
 920         /* Now we need to go through the extendable bucket. Protection is needed
 921          * to protect all extendable bucket processes.
 922          */
 923         __hash_rw_writer_lock(h);
 924         /* We check for duplicates again since could be inserted before the lock */
 925         ret = search_and_update(h, data, key, prim_bkt, short_sig);
 926         if (ret != -1) {
 927                 enqueue_slot_back(h, cached_free_slots, slot_id);
 928                 goto failure;
 929         }
 930
 931         FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
 932                 ret = search_and_update(h, data, key, cur_bkt, short_sig);
 933                 if (ret != -1) {
 934                         enqueue_slot_back(h, cached_free_slots, slot_id);
 935                         goto failure;
 936                 }
 937         }
 938
 939         /* Search sec and ext buckets to find an empty entry to insert. */
 940         FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
 941                 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
 942                         /* Check if slot is available */
 943                         if (likely(cur_bkt->key_idx[i] == EMPTY_SLOT)) {
 944                                 cur_bkt->sig_current[i] = short_sig;
 945                                 cur_bkt->key_idx[i] = new_idx;
 946                                 __hash_rw_writer_unlock(h);
 947                                 return new_idx - 1;
 948                         }
 949                 }
 950         }
 951
 952         /* Failed to get an empty entry from extendable buckets. Link a new
 953          * extendable bucket. We first get a free bucket from ring.
 954          */
 955         if (rte_ring_sc_dequeue(h->free_ext_bkts, &ext_bkt_id) != 0) {
 956                 ret = -ENOSPC;
 957                 goto failure;
 958         }
 959
 960         bkt_id = (uint32_t)((uintptr_t)ext_bkt_id) - 1;
 961         /* Use the first location of the new bucket */
 962         (h->buckets_ext[bkt_id]).sig_current[0] = short_sig;
 963         (h->buckets_ext[bkt_id]).key_idx[0] = new_idx;
 964         /* Link the new bucket to sec bucket linked list */
 965         last = rte_hash_get_last_bkt(sec_bkt);
 966         last->next = &h->buckets_ext[bkt_id];
 967         __hash_rw_writer_unlock(h);
 968         return new_idx - 1;
 969
 970 failure:
 971         __hash_rw_writer_unlock(h);
 972         return ret;
 973
 974 }
 975
 976 int32_t
 977 rte_hash_add_key_with_hash(const struct rte_hash *h,
 978                         const void *key, hash_sig_t sig)
 979 {
 980         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 981         return __rte_hash_add_key_with_hash(h, key, sig, 0);
 982 }
 983
 984 int32_t
 985 rte_hash_add_key(const struct rte_hash *h, const void *key)
 986 {
 987         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 988         return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), 0);
 989 }
 990
 991 int
 992 rte_hash_add_key_with_hash_data(const struct rte_hash *h,
 993                         const void *key, hash_sig_t sig, void *data)
 994 {
 995         int ret;
 996
 997         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 998         ret = __rte_hash_add_key_with_hash(h, key, sig, data);
 999         if (ret >= 0)
1000                 return 0;
1001         else
1002                 return ret;
1003 }
1004
1005 int
1006 rte_hash_add_key_data(const struct rte_hash *h, const void *key, void *data)
1007 {
1008         int ret;
1009
1010         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1011
1012         ret = __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), data);
1013         if (ret >= 0)
1014                 return 0;
1015         else
1016                 return ret;
1017 }
1018
1019 /* Search one bucket to find the match key */
1020 static inline int32_t
1021 search_one_bucket(const struct rte_hash *h, const void *key, uint16_t sig,
1022                         void **data, const struct rte_hash_bucket *bkt)
1023 {
1024         int i;
1025         struct rte_hash_key *k, *keys = h->key_store;
1026
1027         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1028                 if (bkt->sig_current[i] == sig &&
1029                                 bkt->key_idx[i] != EMPTY_SLOT) {
1030                         k = (struct rte_hash_key *) ((char *)keys +
1031                                         bkt->key_idx[i] * h->key_entry_size);
1032                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
1033                                 if (data != NULL)
1034                                         *data = k->pdata;
1035                                 /*
1036                                  * Return index where key is stored,
1037                                  * subtracting the first dummy index
1038                                  */
1039                                 return bkt->key_idx[i] - 1;
1040                         }
1041                 }
1042         }
1043         return -1;
1044 }
1045
1046 static inline int32_t
1047 __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,
1048                                         hash_sig_t sig, void **data)
1049 {
1050         uint32_t prim_bucket_idx, sec_bucket_idx;
1051         struct rte_hash_bucket *bkt, *cur_bkt;
1052         int ret;
1053         uint16_t short_sig;
1054
1055         short_sig = get_short_sig(sig);
1056         prim_bucket_idx = get_prim_bucket_index(h, sig);
1057         sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig);
1058         bkt = &h->buckets[prim_bucket_idx];
1059
1060         __hash_rw_reader_lock(h);
1061
1062         /* Check if key is in primary location */
1063         ret = search_one_bucket(h, key, short_sig, data, bkt);
1064         if (ret != -1) {
1065                 __hash_rw_reader_unlock(h);
1066                 return ret;
1067         }
1068         /* Calculate secondary hash */
1069         bkt = &h->buckets[sec_bucket_idx];
1070
1071         /* Check if key is in secondary location */
1072         FOR_EACH_BUCKET(cur_bkt, bkt) {
1073                 ret = search_one_bucket(h, key, short_sig, data, cur_bkt);
1074                 if (ret != -1) {
1075                         __hash_rw_reader_unlock(h);
1076                         return ret;
1077                 }
1078         }
1079         __hash_rw_reader_unlock(h);
1080         return -ENOENT;
1081 }
1082
1083 int32_t
1084 rte_hash_lookup_with_hash(const struct rte_hash *h,
1085                         const void *key, hash_sig_t sig)
1086 {
1087         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1088         return __rte_hash_lookup_with_hash(h, key, sig, NULL);
1089 }
1090
1091 int32_t
1092 rte_hash_lookup(const struct rte_hash *h, const void *key)
1093 {
1094         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1095         return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), NULL);
1096 }
1097
1098 int
1099 rte_hash_lookup_with_hash_data(const struct rte_hash *h,
1100                         const void *key, hash_sig_t sig, void **data)
1101 {
1102         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1103         return __rte_hash_lookup_with_hash(h, key, sig, data);
1104 }
1105
1106 int
1107 rte_hash_lookup_data(const struct rte_hash *h, const void *key, void **data)
1108 {
1109         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1110         return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), data);
1111 }
1112
1113 static inline void
1114 remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i)
1115 {
1116         unsigned lcore_id, n_slots;
1117         struct lcore_cache *cached_free_slots;
1118
1119         bkt->sig_current[i] = NULL_SIGNATURE;
1120         if (h->multi_writer_support) {
1121                 lcore_id = rte_lcore_id();
1122                 cached_free_slots = &h->local_free_slots[lcore_id];
1123                 /* Cache full, need to free it. */
1124                 if (cached_free_slots->len == LCORE_CACHE_SIZE) {
1125                         /* Need to enqueue the free slots in global ring. */
1126                         n_slots = rte_ring_mp_enqueue_burst(h->free_slots,
1127                                                 cached_free_slots->objs,
1128                                                 LCORE_CACHE_SIZE, NULL);
1129                         cached_free_slots->len -= n_slots;
1130                 }
1131                 /* Put index of new free slot in cache. */
1132                 cached_free_slots->objs[cached_free_slots->len] =
1133                                 (void *)((uintptr_t)bkt->key_idx[i]);
1134                 cached_free_slots->len++;
1135         } else {
1136                 rte_ring_sp_enqueue(h->free_slots,
1137                                 (void *)((uintptr_t)bkt->key_idx[i]));
1138         }
1139 }
1140
1141 /* Compact the linked list by moving key from last entry in linked list to the
1142  * empty slot.
1143  */
1144 static inline void
1145 __rte_hash_compact_ll(struct rte_hash_bucket *cur_bkt, int pos) {
1146         int i;
1147         struct rte_hash_bucket *last_bkt;
1148
1149         if (!cur_bkt->next)
1150                 return;
1151
1152         last_bkt = rte_hash_get_last_bkt(cur_bkt);
1153
1154         for (i = RTE_HASH_BUCKET_ENTRIES - 1; i >= 0; i--) {
1155                 if (last_bkt->key_idx[i] != EMPTY_SLOT) {
1156                         cur_bkt->key_idx[pos] = last_bkt->key_idx[i];
1157                         cur_bkt->sig_current[pos] = last_bkt->sig_current[i];
1158                         last_bkt->sig_current[i] = NULL_SIGNATURE;
1159                         last_bkt->key_idx[i] = EMPTY_SLOT;
1160                         return;
1161                 }
1162         }
1163 }
1164
1165 /* Search one bucket and remove the matched key */
1166 static inline int32_t
1167 search_and_remove(const struct rte_hash *h, const void *key,
1168                         struct rte_hash_bucket *bkt, uint16_t sig, int *pos)
1169 {
1170         struct rte_hash_key *k, *keys = h->key_store;
1171         unsigned int i;
1172         int32_t ret;
1173
1174         /* Check if key is in bucket */
1175         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1176                 if (bkt->sig_current[i] == sig &&
1177                                 bkt->key_idx[i] != EMPTY_SLOT) {
1178                         k = (struct rte_hash_key *) ((char *)keys +
1179                                         bkt->key_idx[i] * h->key_entry_size);
1180                         if (rte_hash_cmp_eq(key, k->key, h) == 0) {
1181                                 remove_entry(h, bkt, i);
1182
1183                                 /* Return index where key is stored,
1184                                  * subtracting the first dummy index
1185                                  */
1186                                 ret = bkt->key_idx[i] - 1;
1187                                 bkt->key_idx[i] = EMPTY_SLOT;
1188                                 *pos = i;
1189                                 return ret;
1190                         }
1191                 }
1192         }
1193         return -1;
1194 }
1195
1196 static inline int32_t
1197 __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,
1198                                                 hash_sig_t sig)
1199 {
1200         uint32_t prim_bucket_idx, sec_bucket_idx;
1201         struct rte_hash_bucket *prim_bkt, *sec_bkt, *prev_bkt, *last_bkt;
1202         struct rte_hash_bucket *cur_bkt;
1203         int pos;
1204         int32_t ret, i;
1205         uint16_t short_sig;
1206
1207         short_sig = get_short_sig(sig);
1208         prim_bucket_idx = get_prim_bucket_index(h, sig);
1209         sec_bucket_idx = get_alt_bucket_index(h, prim_bucket_idx, short_sig);
1210         prim_bkt = &h->buckets[prim_bucket_idx];
1211
1212         __hash_rw_writer_lock(h);
1213         /* look for key in primary bucket */
1214         ret = search_and_remove(h, key, prim_bkt, short_sig, &pos);
1215         if (ret != -1) {
1216                 __rte_hash_compact_ll(prim_bkt, pos);
1217                 last_bkt = prim_bkt->next;
1218                 prev_bkt = prim_bkt;
1219                 goto return_bkt;
1220         }
1221
1222         /* Calculate secondary hash */
1223         sec_bkt = &h->buckets[sec_bucket_idx];
1224
1225         FOR_EACH_BUCKET(cur_bkt, sec_bkt) {
1226                 ret = search_and_remove(h, key, cur_bkt, short_sig, &pos);
1227                 if (ret != -1) {
1228                         __rte_hash_compact_ll(cur_bkt, pos);
1229                         last_bkt = sec_bkt->next;
1230                         prev_bkt = sec_bkt;
1231                         goto return_bkt;
1232                 }
1233         }
1234
1235         __hash_rw_writer_unlock(h);
1236         return -ENOENT;
1237
1238 /* Search last bucket to see if empty to be recycled */
1239 return_bkt:
1240         if (!last_bkt) {
1241                 __hash_rw_writer_unlock(h);
1242                 return ret;
1243         }
1244         while (last_bkt->next) {
1245                 prev_bkt = last_bkt;
1246                 last_bkt = last_bkt->next;
1247         }
1248
1249         for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1250                 if (last_bkt->key_idx[i] != EMPTY_SLOT)
1251                         break;
1252         }
1253         /* found empty bucket and recycle */
1254         if (i == RTE_HASH_BUCKET_ENTRIES) {
1255                 prev_bkt->next = last_bkt->next = NULL;
1256                 uint32_t index = last_bkt - h->buckets_ext + 1;
1257                 rte_ring_sp_enqueue(h->free_ext_bkts, (void *)(uintptr_t)index);
1258         }
1259
1260         __hash_rw_writer_unlock(h);
1261         return ret;
1262 }
1263
1264 int32_t
1265 rte_hash_del_key_with_hash(const struct rte_hash *h,
1266                         const void *key, hash_sig_t sig)
1267 {
1268         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1269         return __rte_hash_del_key_with_hash(h, key, sig);
1270 }
1271
1272 int32_t
1273 rte_hash_del_key(const struct rte_hash *h, const void *key)
1274 {
1275         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1276         return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key));
1277 }
1278
1279 int
1280 rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
1281                                void **key)
1282 {
1283         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
1284
1285         struct rte_hash_key *k, *keys = h->key_store;
1286         k = (struct rte_hash_key *) ((char *) keys + (position + 1) *
1287                                      h->key_entry_size);
1288         *key = k->key;
1289
1290         if (position !=
1291             __rte_hash_lookup_with_hash(h, *key, rte_hash_hash(h, *key),
1292                                         NULL)) {
1293                 return -ENOENT;
1294         }
1295
1296         return 0;
1297 }
1298
1299 static inline void
1300 compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches,
1301                         const struct rte_hash_bucket *prim_bkt,
1302                         const struct rte_hash_bucket *sec_bkt,
1303                         uint16_t sig,
1304                         enum rte_hash_sig_compare_function sig_cmp_fn)
1305 {
1306         unsigned int i;
1307
1308         /* For match mask the first bit of every two bits indicates the match */
1309         switch (sig_cmp_fn) {
1310 #ifdef RTE_MACHINE_CPUFLAG_SSE2
1311         case RTE_HASH_COMPARE_SSE:
1312                 /* Compare all signatures in the bucket */
1313                 *prim_hash_matches = _mm_movemask_epi8(_mm_cmpeq_epi16(
1314                                 _mm_load_si128(
1315                                         (__m128i const *)prim_bkt->sig_current),
1316                                 _mm_set1_epi16(sig)));
1317                 /* Compare all signatures in the bucket */
1318                 *sec_hash_matches = _mm_movemask_epi8(_mm_cmpeq_epi16(
1319                                 _mm_load_si128(
1320                                         (__m128i const *)sec_bkt->sig_current),
1321                                 _mm_set1_epi16(sig)));
1322                 break;
1323 #endif
1324         default:
1325                 for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
1326                         *prim_hash_matches |=
1327                                 ((sig == prim_bkt->sig_current[i]) << (i << 1));
1328                         *sec_hash_matches |=
1329                                 ((sig == sec_bkt->sig_current[i]) << (i << 1));
1330                 }
1331         }
1332 }
1333
1334 #define PREFETCH_OFFSET 4
1335 static inline void
1336 __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
1337                         int32_t num_keys, int32_t *positions,
1338                         uint64_t *hit_mask, void *data[])
1339 {
1340         uint64_t hits = 0;
1341         int32_t i;
1342         int32_t ret;
1343         uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX];
1344         uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX];
1345         uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX];
1346         uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX];
1347         const struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
1348         const struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];
1349         uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
1350         uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};
1351         struct rte_hash_bucket *cur_bkt, *next_bkt;
1352
1353         /* Prefetch first keys */
1354         for (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++)
1355                 rte_prefetch0(keys[i]);
1356
1357         /*
1358          * Prefetch rest of the keys, calculate primary and
1359          * secondary bucket and prefetch them
1360          */
1361         for (i = 0; i < (num_keys - PREFETCH_OFFSET); i++) {
1362                 rte_prefetch0(keys[i + PREFETCH_OFFSET]);
1363
1364                 prim_hash[i] = rte_hash_hash(h, keys[i]);
1365
1366                 sig[i] = get_short_sig(prim_hash[i]);
1367                 prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
1368                 sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
1369
1370                 primary_bkt[i] = &h->buckets[prim_index[i]];
1371                 secondary_bkt[i] = &h->buckets[sec_index[i]];
1372
1373                 rte_prefetch0(primary_bkt[i]);
1374                 rte_prefetch0(secondary_bkt[i]);
1375         }
1376
1377         /* Calculate and prefetch rest of the buckets */
1378         for (; i < num_keys; i++) {
1379                 prim_hash[i] = rte_hash_hash(h, keys[i]);
1380
1381                 sig[i] = get_short_sig(prim_hash[i]);
1382                 prim_index[i] = get_prim_bucket_index(h, prim_hash[i]);
1383                 sec_index[i] = get_alt_bucket_index(h, prim_index[i], sig[i]);
1384
1385                 primary_bkt[i] = &h->buckets[prim_index[i]];
1386                 secondary_bkt[i] = &h->buckets[sec_index[i]];
1387
1388                 rte_prefetch0(primary_bkt[i]);
1389                 rte_prefetch0(secondary_bkt[i]);
1390         }
1391
1392         __hash_rw_reader_lock(h);
1393         /* Compare signatures and prefetch key slot of first hit */
1394         for (i = 0; i < num_keys; i++) {
1395                 compare_signatures(&prim_hitmask[i], &sec_hitmask[i],
1396                                 primary_bkt[i], secondary_bkt[i],
1397                                 sig[i], h->sig_cmp_fn);
1398
1399                 if (prim_hitmask[i]) {
1400                         uint32_t first_hit =
1401                                         __builtin_ctzl(prim_hitmask[i]) >> 1;
1402                         uint32_t key_idx = primary_bkt[i]->key_idx[first_hit];
1403                         const struct rte_hash_key *key_slot =
1404                                 (const struct rte_hash_key *)(
1405                                 (const char *)h->key_store +
1406                                 key_idx * h->key_entry_size);
1407                         rte_prefetch0(key_slot);
1408                         continue;
1409                 }
1410
1411                 if (sec_hitmask[i]) {
1412                         uint32_t first_hit =
1413                                         __builtin_ctzl(sec_hitmask[i]) >> 1;
1414                         uint32_t key_idx = secondary_bkt[i]->key_idx[first_hit];
1415                         const struct rte_hash_key *key_slot =
1416                                 (const struct rte_hash_key *)(
1417                                 (const char *)h->key_store +
1418                                 key_idx * h->key_entry_size);
1419                         rte_prefetch0(key_slot);
1420                 }
1421         }
1422
1423         /* Compare keys, first hits in primary first */
1424         for (i = 0; i < num_keys; i++) {
1425                 positions[i] = -ENOENT;
1426                 while (prim_hitmask[i]) {
1427                         uint32_t hit_index =
1428                                         __builtin_ctzl(prim_hitmask[i]) >> 1;
1429
1430                         uint32_t key_idx = primary_bkt[i]->key_idx[hit_index];
1431                         const struct rte_hash_key *key_slot =
1432                                 (const struct rte_hash_key *)(
1433                                 (const char *)h->key_store +
1434                                 key_idx * h->key_entry_size);
1435                         /*
1436                          * If key index is 0, do not compare key,
1437                          * as it is checking the dummy slot
1438                          */
1439                         if (!!key_idx & !rte_hash_cmp_eq(key_slot->key, keys[i], h)) {
1440                                 if (data != NULL)
1441                                         data[i] = key_slot->pdata;
1442
1443                                 hits |= 1ULL << i;
1444                                 positions[i] = key_idx - 1;
1445                                 goto next_key;
1446                         }
1447                         prim_hitmask[i] &= ~(3ULL << (hit_index << 1));
1448                 }
1449
1450                 while (sec_hitmask[i]) {
1451                         uint32_t hit_index =
1452                                         __builtin_ctzl(sec_hitmask[i]) >> 1;
1453
1454                         uint32_t key_idx = secondary_bkt[i]->key_idx[hit_index];
1455                         const struct rte_hash_key *key_slot =
1456                                 (const struct rte_hash_key *)(
1457                                 (const char *)h->key_store +
1458                                 key_idx * h->key_entry_size);
1459                         /*
1460                          * If key index is 0, do not compare key,
1461                          * as it is checking the dummy slot
1462                          */
1463
1464                         if (!!key_idx & !rte_hash_cmp_eq(key_slot->key, keys[i], h)) {
1465                                 if (data != NULL)
1466                                         data[i] = key_slot->pdata;
1467
1468                                 hits |= 1ULL << i;
1469                                 positions[i] = key_idx - 1;
1470                                 goto next_key;
1471                         }
1472                         sec_hitmask[i] &= ~(3ULL << (hit_index << 1));
1473                 }
1474
1475 next_key:
1476                 continue;
1477         }
1478
1479         /* all found, do not need to go through ext bkt */
1480         if ((hits == ((1ULL << num_keys) - 1)) || !h->ext_table_support) {
1481                 if (hit_mask != NULL)
1482                         *hit_mask = hits;
1483                 __hash_rw_reader_unlock(h);
1484                 return;
1485         }
1486
1487         /* need to check ext buckets for match */
1488         for (i = 0; i < num_keys; i++) {
1489                 if ((hits & (1ULL << i)) != 0)
1490                         continue;
1491                 next_bkt = secondary_bkt[i]->next;
1492                 FOR_EACH_BUCKET(cur_bkt, next_bkt) {
1493                         if (data != NULL)
1494                                 ret = search_one_bucket(h, keys[i],
1495                                                 sig[i], &data[i], cur_bkt);
1496                         else
1497                                 ret = search_one_bucket(h, keys[i],
1498                                                 sig[i], NULL, cur_bkt);
1499                         if (ret != -1) {
1500                                 positions[i] = ret;
1501                                 hits |= 1ULL << i;
1502                                 break;
1503                         }
1504                 }
1505         }
1506
1507         __hash_rw_reader_unlock(h);
1508
1509         if (hit_mask != NULL)
1510                 *hit_mask = hits;
1511 }
1512
1513 int
1514 rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
1515                       uint32_t num_keys, int32_t *positions)
1516 {
1517         RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
1518                         (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
1519                         (positions == NULL)), -EINVAL);
1520
1521         __rte_hash_lookup_bulk(h, keys, num_keys, positions, NULL, NULL);
1522         return 0;
1523 }
1524
1525 int
1526 rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys,
1527                       uint32_t num_keys, uint64_t *hit_mask, void *data[])
1528 {
1529         RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
1530                         (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
1531                         (hit_mask == NULL)), -EINVAL);
1532
1533         int32_t positions[num_keys];
1534
1535         __rte_hash_lookup_bulk(h, keys, num_keys, positions, hit_mask, data);
1536
1537         /* Return number of hits */
1538         return __builtin_popcountl(*hit_mask);
1539 }
1540
1541 int32_t
1542 rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next)
1543 {
1544         uint32_t bucket_idx, idx, position;
1545         struct rte_hash_key *next_key;
1546
1547         RETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL);
1548
1549         const uint32_t total_entries_main = h->num_buckets *
1550                                                         RTE_HASH_BUCKET_ENTRIES;
1551         const uint32_t total_entries = total_entries_main << 1;
1552
1553         /* Out of bounds of all buckets (both main table and ext table) */
1554         if (*next >= total_entries_main)
1555                 goto extend_table;
1556
1557         /* Calculate bucket and index of current iterator */
1558         bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
1559         idx = *next % RTE_HASH_BUCKET_ENTRIES;
1560
1561         /* If current position is empty, go to the next one */
1562         while ((position = h->buckets[bucket_idx].key_idx[idx]) == EMPTY_SLOT) {
1563                 (*next)++;
1564                 /* End of table */
1565                 if (*next == total_entries_main)
1566                         goto extend_table;
1567                 bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
1568                 idx = *next % RTE_HASH_BUCKET_ENTRIES;
1569         }
1570
1571         __hash_rw_reader_lock(h);
1572         next_key = (struct rte_hash_key *) ((char *)h->key_store +
1573                                 position * h->key_entry_size);
1574         /* Return key and data */
1575         *key = next_key->key;
1576         *data = next_key->pdata;
1577
1578         __hash_rw_reader_unlock(h);
1579
1580         /* Increment iterator */
1581         (*next)++;
1582
1583         return position - 1;
1584
1585 /* Begin to iterate extendable buckets */
1586 extend_table:
1587         /* Out of total bound or if ext bucket feature is not enabled */
1588         if (*next >= total_entries || !h->ext_table_support)
1589                 return -ENOENT;
1590
1591         bucket_idx = (*next - total_entries_main) / RTE_HASH_BUCKET_ENTRIES;
1592         idx = (*next - total_entries_main) % RTE_HASH_BUCKET_ENTRIES;
1593
1594         while ((position = h->buckets_ext[bucket_idx].key_idx[idx]) == EMPTY_SLOT) {
1595                 (*next)++;
1596                 if (*next == total_entries)
1597                         return -ENOENT;
1598                 bucket_idx = (*next - total_entries_main) /
1599                                                 RTE_HASH_BUCKET_ENTRIES;
1600                 idx = (*next - total_entries_main) % RTE_HASH_BUCKET_ENTRIES;
1601         }
1602         __hash_rw_reader_lock(h);
1603         next_key = (struct rte_hash_key *) ((char *)h->key_store +
1604                                 position * h->key_entry_size);
1605         /* Return key and data */
1606         *key = next_key->key;
1607         *data = next_key->pdata;
1608
1609         __hash_rw_reader_unlock(h);
1610
1611         /* Increment iterator */
1612         (*next)++;
1613         return position - 1;
1614 }