LCOV - code coverage report
Current view: top level - lib/hash - rte_cuckoo_hash.c (source / functions) Hit Total Coverage
Test: Code coverage Lines: 696 1006 69.2 %
Date: 2024-04-01 19:00:53 Functions: 49 61 80.3 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 337 517 65.2 %

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

Generated by: LCOV version 1.14