drivers/net/bnxt/tf_ulp/ulp_gen_hash.c

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