LCOV - code coverage report
Current view: top level - drivers/net/bnxt/tf_ulp - ulp_gen_hash.c (source / functions) Hit Total Coverage
Test: Code coverage Lines: 0 160 0.0 %
Date: 2024-02-14 00:53:57 Functions: 0 8 0.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 70 0.0 %

           Branch data     Line data    Source code
       1                 :            : /* SPDX-License-Identifier: BSD-3-Clause
       2                 :            :  * Copyright(c) 2014-2023 Broadcom
       3                 :            :  * All rights reserved.
       4                 :            :  */
       5                 :            : 
       6                 :            : #include <rte_log.h>
       7                 :            : #include <rte_malloc.h>
       8                 :            : #include "bnxt_tf_common.h"
       9                 :            : #include "ulp_gen_hash.h"
      10                 :            : #include "ulp_utils.h"
      11                 :            : #include "tf_hash.h"
      12                 :            : 
      13                 :            : static
      14                 :          0 : int32_t ulp_bit_alloc_list_alloc(struct bit_alloc_list *blist,
      15                 :            :                                  uint32_t *index)
      16                 :            : {
      17                 :            :         uint64_t bentry;
      18                 :            :         uint32_t idx = 0, jdx = 0;
      19                 :          0 :         uint32_t bsize_64 = blist->bsize / ULP_64B_IN_BYTES;
      20                 :            : 
      21                 :            :         /* Iterate all numbers that have all 1's */
      22                 :            :         do {
      23                 :          0 :                 bentry = blist->bdata[idx++];
      24         [ #  # ]:          0 :         } while (bentry == -1UL && idx <= bsize_64);
      25                 :            : 
      26         [ #  # ]:          0 :         if (idx <= bsize_64) {
      27         [ #  # ]:          0 :                 if (bentry)
      28                 :          0 :                         jdx = __builtin_clzl(~bentry);
      29                 :          0 :                 *index = ((idx - 1) * ULP_INDEX_BITMAP_SIZE) + jdx;
      30                 :          0 :                 ULP_INDEX_BITMAP_SET(blist->bdata[(idx - 1)], jdx);
      31                 :          0 :                 return 0;
      32                 :            :         }
      33                 :          0 :         jdx = (uint32_t)(bsize_64 * ULP_INDEX_BITMAP_SIZE);
      34                 :          0 :         BNXT_TF_DBG(ERR, "bit allocator is full reached max:%x\n", jdx);
      35                 :          0 :         return -1;
      36                 :            : }
      37                 :            : 
      38                 :            : static
      39                 :          0 : int32_t ulp_bit_alloc_list_dealloc(struct bit_alloc_list *blist,
      40                 :            :                                    uint32_t index)
      41                 :            : {
      42                 :            :         uint32_t idx = 0, jdx;
      43                 :          0 :         uint32_t bsize_64 = blist->bsize / ULP_64B_IN_BYTES;
      44                 :            : 
      45                 :          0 :         idx = index / ULP_INDEX_BITMAP_SIZE;
      46         [ #  # ]:          0 :         if (idx >= bsize_64) {
      47                 :          0 :                 BNXT_TF_DBG(ERR, "invalid bit index %x:%x\n", idx,
      48                 :            :                             blist->bsize);
      49                 :          0 :                 return -EINVAL;
      50                 :            :         }
      51                 :            :         jdx = index % ULP_INDEX_BITMAP_SIZE;
      52                 :          0 :         ULP_INDEX_BITMAP_RESET(blist->bdata[idx], jdx);
      53                 :          0 :         return 0;
      54                 :            : }
      55                 :            : 
      56                 :            : /*
      57                 :            :  * Initialize the Generic Hash table
      58                 :            :  *
      59                 :            :  * cparams [in] Pointer to hash create params list
      60                 :            :  * hash_tbl [out] the pointer to created hash table
      61                 :            :  *
      62                 :            :  * returns 0 on success
      63                 :            :  */
      64                 :            : int32_t
      65                 :          0 : ulp_gen_hash_tbl_list_init(struct ulp_hash_create_params *cparams,
      66                 :            :                            struct ulp_gen_hash_tbl **hash_table)
      67                 :            : {
      68                 :            :         struct ulp_gen_hash_tbl *hash_tbl = NULL;
      69                 :            :         int32_t rc = 0;
      70                 :            :         uint32_t size = 0;
      71                 :            : 
      72                 :            :         /* validate the arguments */
      73         [ #  # ]:          0 :         if (!hash_table || !cparams) {
      74                 :          0 :                 BNXT_TF_DBG(ERR, "invalid arguments\n");
      75                 :          0 :                 return -EINVAL;
      76                 :            :         }
      77                 :            : 
      78                 :            :         /* validate the size parameters */
      79   [ #  #  #  # ]:          0 :         if (ulp_util_is_power_of_2(cparams->num_hash_tbl_entries) ||
      80                 :          0 :             ulp_util_is_power_of_2(cparams->num_key_entries) ||
      81         [ #  # ]:          0 :             (cparams->num_buckets % ULP_HASH_BUCKET_ROW_SZ)) {
      82                 :          0 :                 BNXT_TF_DBG(ERR, "invalid arguments for hash tbl\n");
      83                 :          0 :                 return -EINVAL;
      84                 :            :         }
      85                 :            : 
      86                 :            :         /* validate the size of the hash table size */
      87         [ #  # ]:          0 :         if (cparams->num_hash_tbl_entries >= ULP_GEN_HASH_MAX_TBL_SIZE) {
      88                 :          0 :                 BNXT_TF_DBG(ERR, "invalid size for hash tbl\n");
      89                 :          0 :                 return -EINVAL;
      90                 :            :         }
      91                 :            : 
      92                 :          0 :         hash_tbl = rte_zmalloc("Generic hash table",
      93                 :            :                                sizeof(struct ulp_gen_hash_tbl), 0);
      94         [ #  # ]:          0 :         if (!hash_tbl) {
      95                 :          0 :                 BNXT_TF_DBG(ERR, "failed to alloc mem for hash tbl\n");
      96                 :          0 :                 return -ENOMEM;
      97                 :            :         }
      98                 :          0 :         *hash_table = hash_tbl;
      99                 :            :         /* allocate the memory for the hash key table */
     100                 :          0 :         hash_tbl->num_key_entries = cparams->num_key_entries;
     101                 :          0 :         hash_tbl->key_tbl.data_size = cparams->key_size;
     102                 :          0 :         hash_tbl->key_tbl.mem_size = cparams->key_size *
     103                 :          0 :                 (cparams->num_key_entries + 1);
     104                 :          0 :         hash_tbl->key_tbl.key_data = rte_zmalloc("Generic hash keys",
     105                 :            :                                                  hash_tbl->key_tbl.mem_size, 0);
     106         [ #  # ]:          0 :         if (!hash_tbl->key_tbl.key_data) {
     107                 :          0 :                 BNXT_TF_DBG(ERR, "failed to alloc mem for hash key\n");
     108                 :            :                 rc = -ENOMEM;
     109                 :          0 :                 goto init_error;
     110                 :            :         }
     111                 :            : 
     112                 :            :         /* allocate the memory for the hash table */
     113                 :          0 :         hash_tbl->hash_bkt_num = cparams->num_buckets / ULP_HASH_BUCKET_ROW_SZ;
     114                 :          0 :         hash_tbl->hash_tbl_size = cparams->num_hash_tbl_entries;
     115                 :          0 :         size = hash_tbl->hash_tbl_size * hash_tbl->hash_bkt_num *
     116                 :            :                 sizeof(struct ulp_hash_bucket_entry);
     117                 :          0 :         hash_tbl->hash_list = rte_zmalloc("Generic hash table list", size,
     118                 :            :                                           ULP_BUFFER_ALIGN_64_BYTE);
     119         [ #  # ]:          0 :         if (!hash_tbl->hash_list) {
     120                 :          0 :                 BNXT_TF_DBG(ERR, "failed to alloc mem for hash tbl\n");
     121                 :            :                 rc = -ENOMEM;
     122                 :          0 :                 goto init_error;
     123                 :            :         }
     124                 :            : 
     125                 :            :         /* calculate the hash_mask based on the tbl size */
     126                 :            :         size = 1;
     127         [ #  # ]:          0 :         while (size < hash_tbl->hash_tbl_size)
     128                 :          0 :                 size = size << 1;
     129                 :          0 :         hash_tbl->hash_mask = size - 1;
     130                 :            : 
     131                 :            :         /* allocate the memory for the bit allocator */
     132                 :          0 :         size = (cparams->num_key_entries / sizeof(uint64_t));
     133                 :          0 :         size = ULP_BYTE_ROUND_OFF_8(size);
     134                 :          0 :         hash_tbl->bit_list.bsize = size;
     135                 :          0 :         hash_tbl->bit_list.bdata = rte_zmalloc("Generic hash bit alloc", size,
     136                 :            :                                                ULP_BUFFER_ALIGN_64_BYTE);
     137         [ #  # ]:          0 :         if (!hash_tbl->bit_list.bdata) {
     138                 :          0 :                 BNXT_TF_DBG(ERR, "failed to alloc mem for hash bit list\n");
     139                 :            :                 rc = -ENOMEM;
     140                 :          0 :                 goto init_error;
     141                 :            :         }
     142                 :            :         return rc;
     143                 :            : 
     144                 :          0 : init_error:
     145                 :            :         if (hash_tbl)
     146                 :          0 :                 ulp_gen_hash_tbl_list_deinit(hash_tbl);
     147                 :          0 :         return rc;
     148                 :            : }
     149                 :            : 
     150                 :            : /*
     151                 :            :  * Free the generic hash table
     152                 :            :  *
     153                 :            :  * hash_tbl [in] the pointer to hash table
     154                 :            :  *
     155                 :            :  * returns 0 on success
     156                 :            :  */
     157                 :            : int32_t
     158                 :          0 : ulp_gen_hash_tbl_list_deinit(struct ulp_gen_hash_tbl *hash_tbl)
     159                 :            : {
     160         [ #  # ]:          0 :         if (!hash_tbl)
     161                 :            :                 return -EINVAL;
     162                 :            : 
     163         [ #  # ]:          0 :         if (hash_tbl->key_tbl.key_data) {
     164                 :          0 :                 rte_free(hash_tbl->key_tbl.key_data);
     165                 :          0 :                 hash_tbl->key_tbl.key_data = NULL;
     166                 :            :         }
     167                 :            : 
     168         [ #  # ]:          0 :         if (hash_tbl->hash_list) {
     169                 :          0 :                 rte_free(hash_tbl->hash_list);
     170                 :          0 :                 hash_tbl->hash_list = NULL;
     171                 :            :         }
     172                 :            : 
     173         [ #  # ]:          0 :         if (hash_tbl->bit_list.bdata) {
     174                 :          0 :                 rte_free(hash_tbl->bit_list.bdata);
     175                 :          0 :                 hash_tbl->bit_list.bdata = NULL;
     176                 :            :         }
     177                 :            : 
     178                 :          0 :         rte_free(hash_tbl);
     179                 :          0 :         return 0;
     180                 :            : }
     181                 :            : 
     182                 :            : /*
     183                 :            :  * Search the generic hash table using key data
     184                 :            :  *
     185                 :            :  * hash_tbl [in] the pointer to hash table
     186                 :            :  * entry [in/out] pointer to hash entry details.
     187                 :            :  *
     188                 :            :  * returns 0 on success and marks search flag as found.
     189                 :            :  */
     190                 :            : int32_t
     191                 :          0 : ulp_gen_hash_tbl_list_key_search(struct ulp_gen_hash_tbl *hash_tbl,
     192                 :            :                                  struct ulp_gen_hash_entry_params *entry)
     193                 :            : {
     194                 :            :         uint32_t hash_id, key_idx, idx;
     195                 :            :         uint16_t *bucket;
     196                 :            :         int32_t miss_idx = ULP_HASH_BUCKET_INVAL;
     197                 :            : 
     198                 :            :         /* validate the arguments */
     199   [ #  #  #  # ]:          0 :         if (!hash_tbl || !entry || !entry->key_data || entry->key_length !=
     200         [ #  # ]:          0 :             hash_tbl->key_tbl.data_size) {
     201                 :          0 :                 BNXT_TF_DBG(ERR, "invalid arguments\n");
     202                 :          0 :                 return -EINVAL;
     203                 :            :         }
     204                 :            : 
     205                 :            :         /* calculate the hash */
     206                 :          0 :         hash_id = tf_hash_calc_crc32(entry->key_data,
     207                 :            :                                      hash_tbl->key_tbl.data_size);
     208                 :          0 :         hash_id = (uint16_t)(((hash_id >> 16) & 0xffff) ^ (hash_id & 0xffff));
     209                 :          0 :         hash_id &= hash_tbl->hash_mask;
     210                 :          0 :         hash_id = hash_id * hash_tbl->hash_bkt_num;
     211                 :            : 
     212                 :            :         /* Iterate the bucket list */
     213                 :          0 :         bucket = (uint16_t *)&hash_tbl->hash_list[hash_id];
     214         [ #  # ]:          0 :         for (idx = 0; idx < (hash_tbl->hash_bkt_num * ULP_HASH_BUCKET_ROW_SZ);
     215                 :          0 :               idx++, bucket++) {
     216         [ #  # ]:          0 :                 if (ULP_HASH_BUCKET_INUSE(bucket)) {
     217                 :            :                         /* compare the key contents */
     218                 :          0 :                         key_idx = ULP_HASH_BUCKET_INDEX(bucket);
     219         [ #  # ]:          0 :                         if (key_idx >= hash_tbl->num_key_entries) {
     220                 :          0 :                                 BNXT_TF_DBG(ERR, "Hash table corruption\n");
     221                 :          0 :                                 return -EINVAL;
     222                 :            :                         }
     223                 :          0 :                         if (!memcmp(entry->key_data,
     224                 :          0 :                                     &hash_tbl->key_tbl.key_data[key_idx *
     225                 :            :                                     hash_tbl->key_tbl.data_size],
     226         [ #  # ]:          0 :                                     hash_tbl->key_tbl.data_size)) {
     227                 :            :                                 /* Found the entry */
     228                 :          0 :                                 entry->search_flag = ULP_GEN_HASH_SEARCH_FOUND;
     229                 :          0 :                                 entry->hash_index = ULP_HASH_INDEX_CALC(hash_id,
     230                 :            :                                                                         idx);
     231                 :          0 :                                 entry->key_idx = key_idx;
     232                 :          0 :                                 return 0;
     233                 :            :                         }
     234         [ #  # ]:          0 :                 } else if (miss_idx == ULP_HASH_BUCKET_INVAL) {
     235                 :          0 :                         miss_idx = idx;
     236                 :            :                 }
     237                 :            :         }
     238                 :            : 
     239         [ #  # ]:          0 :         if (miss_idx == ULP_HASH_BUCKET_INVAL) {
     240                 :          0 :                 entry->search_flag = ULP_GEN_HASH_SEARCH_FULL;
     241                 :            :         } else {
     242                 :          0 :                 entry->search_flag = ULP_GEN_HASH_SEARCH_MISSED;
     243                 :          0 :                 entry->hash_index = ULP_HASH_INDEX_CALC(hash_id, miss_idx);
     244                 :            :         }
     245                 :            :         return 0;
     246                 :            : }
     247                 :            : 
     248                 :            : /*
     249                 :            :  * Search the generic hash table using hash index
     250                 :            :  *
     251                 :            :  * hash_tbl [in] the pointer to hash table
     252                 :            :  * entry [in/out] pointer to hash entry details.
     253                 :            :  *
     254                 :            :  * returns 0 on success and marks search flag as found.
     255                 :            :  */
     256                 :            : int32_t
     257                 :          0 : ulp_gen_hash_tbl_list_index_search(struct ulp_gen_hash_tbl *hash_tbl,
     258                 :            :                                    struct ulp_gen_hash_entry_params *entry)
     259                 :            : {
     260                 :            :         uint32_t idx;
     261                 :            :         uint16_t *bucket;
     262                 :            : 
     263                 :            :         /* validate the arguments */
     264         [ #  # ]:          0 :         if (!hash_tbl || !entry) {
     265                 :          0 :                 BNXT_TF_DBG(ERR, "invalid arguments\n");
     266                 :          0 :                 return -EINVAL;
     267                 :            :         }
     268                 :            : 
     269                 :          0 :         idx = ULP_HASH_GET_H_INDEX(entry->hash_index);
     270         [ #  # ]:          0 :         if (idx > (hash_tbl->hash_tbl_size * hash_tbl->hash_bkt_num)) {
     271                 :          0 :                 BNXT_TF_DBG(ERR, "invalid hash index %x\n", idx);
     272                 :          0 :                 return -EINVAL;
     273                 :            :         }
     274                 :          0 :         bucket = (uint16_t *)&hash_tbl->hash_list[idx];
     275                 :          0 :         idx  = ULP_HASH_GET_B_INDEX(entry->hash_index);
     276         [ #  # ]:          0 :         if (idx >= (hash_tbl->hash_bkt_num * ULP_HASH_BUCKET_ROW_SZ)) {
     277                 :          0 :                 BNXT_TF_DBG(ERR, "invalid bucket index %x\n", idx);
     278                 :          0 :                 return -EINVAL;
     279                 :            :         }
     280                 :          0 :         bucket += idx;
     281         [ #  # ]:          0 :         if (ULP_HASH_BUCKET_INUSE(bucket)) {
     282                 :          0 :                 entry->key_idx = ULP_HASH_BUCKET_INDEX(bucket);
     283                 :          0 :                 entry->search_flag = ULP_GEN_HASH_SEARCH_FOUND;
     284                 :            :         } else {
     285                 :          0 :                 entry->search_flag = ULP_GEN_HASH_SEARCH_MISSED;
     286                 :          0 :                 return -ENOENT;
     287                 :            :         }
     288                 :          0 :         return 0;
     289                 :            : }
     290                 :            : 
     291                 :            : /*
     292                 :            :  * Add the entry to the generic hash table
     293                 :            :  *
     294                 :            :  * hash_tbl [in] the pointer to hash table
     295                 :            :  * entry [in/out] pointer to hash entry details. Fill the hash index and
     296                 :            :  * key data details to be added.
     297                 :            :  *
     298                 :            :  * returns 0 on success
     299                 :            :  *
     300                 :            :  */
     301                 :            : int32_t
     302                 :          0 : ulp_gen_hash_tbl_list_add(struct ulp_gen_hash_tbl *hash_tbl,
     303                 :            :                           struct ulp_gen_hash_entry_params *entry)
     304                 :            : {
     305                 :            :         int32_t rc = 0;
     306                 :            :         uint16_t *bucket;
     307                 :            :         uint32_t idx, key_index;
     308                 :            : 
     309                 :            :         /* add the entry */
     310                 :          0 :         idx = ULP_HASH_GET_H_INDEX(entry->hash_index);
     311                 :          0 :         bucket = (uint16_t *)&hash_tbl->hash_list[idx];
     312                 :          0 :         bucket += ULP_HASH_GET_B_INDEX(entry->hash_index);
     313         [ #  # ]:          0 :         if (ulp_bit_alloc_list_alloc(&hash_tbl->bit_list, &key_index)) {
     314                 :          0 :                 BNXT_TF_DBG(ERR, "Error in bit list alloc\n");
     315                 :          0 :                 return -ENOMEM;
     316                 :            :         }
     317         [ #  # ]:          0 :         if (key_index > hash_tbl->num_key_entries) {
     318                 :          0 :                 BNXT_TF_DBG(ERR, "reached max size %u:%u\n", key_index,
     319                 :            :                             hash_tbl->num_key_entries);
     320                 :          0 :                 ulp_bit_alloc_list_dealloc(&hash_tbl->bit_list, key_index);
     321                 :          0 :                 return -ENOMEM;
     322                 :            :         }
     323                 :            :         /* Update the hash entry */
     324                 :          0 :         ULP_HASH_BUCKET_MARK_INUSE(bucket, (uint16_t)key_index);
     325                 :            : 
     326                 :            :         /* update the hash key and key index */
     327                 :          0 :         entry->key_idx = key_index;
     328                 :          0 :         key_index = key_index * hash_tbl->key_tbl.data_size;
     329                 :          0 :         memcpy(&hash_tbl->key_tbl.key_data[key_index], entry->key_data,
     330                 :            :                hash_tbl->key_tbl.data_size);
     331                 :            : 
     332                 :          0 :         return rc;
     333                 :            : }
     334                 :            : 
     335                 :            : /*
     336                 :            :  * Delete the entry in the generic hash table
     337                 :            :  *
     338                 :            :  * hash_tbl [in] the pointer to hash table
     339                 :            :  * entry [in] pointer to hash entry details. Fill the hash index details to be
     340                 :            :  * deleted.
     341                 :            :  *
     342                 :            :  * returns 0 on success
     343                 :            :  */
     344                 :            : int32_t
     345                 :          0 : ulp_gen_hash_tbl_list_del(struct ulp_gen_hash_tbl *hash_tbl,
     346                 :            :                           struct ulp_gen_hash_entry_params *entry)
     347                 :            : {
     348                 :            :         uint16_t *bucket;
     349                 :            :         uint32_t idx, key_index;
     350                 :            : 
     351                 :            :         /* delete the entry */
     352                 :          0 :         idx = ULP_HASH_GET_H_INDEX(entry->hash_index);
     353                 :          0 :         bucket = (uint16_t *)&hash_tbl->hash_list[idx];
     354                 :          0 :         bucket += ULP_HASH_GET_B_INDEX(entry->hash_index);
     355                 :            : 
     356                 :            :         /* Get the hash entry */
     357                 :          0 :         key_index = ULP_HASH_BUCKET_INDEX(bucket);
     358         [ #  # ]:          0 :         if (key_index >= hash_tbl->num_key_entries) {
     359                 :          0 :                 BNXT_TF_DBG(ERR, "Hash table corruption\n");
     360                 :          0 :                 return -EINVAL;
     361                 :            :         }
     362                 :            : 
     363                 :            :         /* reset the bit in the bit allocator */
     364         [ #  # ]:          0 :         if (ulp_bit_alloc_list_dealloc(&hash_tbl->bit_list,
     365                 :            :                                        key_index)) {
     366                 :          0 :                 BNXT_TF_DBG(ERR, "Error is bit list dealloc\n");
     367                 :          0 :                 return -EINVAL;
     368                 :            :         }
     369                 :            : 
     370                 :            :         /* erase key details and bucket details */
     371                 :          0 :         key_index = key_index * hash_tbl->key_tbl.data_size;
     372                 :          0 :         memset(&hash_tbl->key_tbl.key_data[key_index], 0,
     373                 :            :                hash_tbl->key_tbl.data_size);
     374                 :          0 :         ULP_HASH_BUCKET_CLEAR(bucket);
     375                 :            : 
     376                 :          0 :         return 0;
     377                 :            : }

Generated by: LCOV version 1.14