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         uint32_t bsize_64 = blist->bsize / ULP_64B_IN_BYTES;
  20
  21         /* Iterate all numbers that have all 1's */
  22         do {
  23                 bentry = blist->bdata[idx++];
  24         } while (bentry == -1UL && idx <= bsize_64);
  25
  26         if (idx <= bsize_64) {
  27                 if (bentry)
  28                         jdx = __builtin_clzl(~bentry);
  29                 *index = ((idx - 1) * ULP_INDEX_BITMAP_SIZE) + jdx;
  30                 ULP_INDEX_BITMAP_SET(blist->bdata[(idx - 1)], jdx);
  31                 return 0;
  32         }
  33         jdx = (uint32_t)(bsize_64 * ULP_INDEX_BITMAP_SIZE);
  34         BNXT_TF_DBG(ERR, "bit allocator is full reached max:%x\n", jdx);
  35         return -1;
  36 }
  37
  38 static
  39 int32_t ulp_bit_alloc_list_dealloc(struct bit_alloc_list *blist,
  40                                    uint32_t index)
  41 {
  42         uint32_t idx = 0, jdx;
  43         uint32_t bsize_64 = blist->bsize / ULP_64B_IN_BYTES;
  44
  45         idx = index / ULP_INDEX_BITMAP_SIZE;
  46         if (idx >= bsize_64) {
  47                 BNXT_TF_DBG(ERR, "invalid bit index %x:%x\n", idx,
  48                             blist->bsize);
  49                 return -EINVAL;
  50         }
  51         jdx = index % ULP_INDEX_BITMAP_SIZE;
  52         ULP_INDEX_BITMAP_RESET(blist->bdata[idx], jdx);
  53         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 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         if (!hash_table || !cparams) {
  74                 BNXT_TF_DBG(ERR, "invalid arguments\n");
  75                 return -EINVAL;
  76         }
  77
  78         /* validate the size parameters */
  79         if (ulp_util_is_power_of_2(cparams->num_hash_tbl_entries) ||
  80             ulp_util_is_power_of_2(cparams->num_key_entries) ||
  81             (cparams->num_buckets % ULP_HASH_BUCKET_ROW_SZ)) {
  82                 BNXT_TF_DBG(ERR, "invalid arguments for hash tbl\n");
  83                 return -EINVAL;
  84         }
  85
  86         /* validate the size of the hash table size */
  87         if (cparams->num_hash_tbl_entries >= ULP_GEN_HASH_MAX_TBL_SIZE) {
  88                 BNXT_TF_DBG(ERR, "invalid size for hash tbl\n");
  89                 return -EINVAL;
  90         }
  91
  92         hash_tbl = rte_zmalloc("Generic hash table",
  93                                sizeof(struct ulp_gen_hash_tbl), 0);
  94         if (!hash_tbl) {
  95                 BNXT_TF_DBG(ERR, "failed to alloc mem for hash tbl\n");
  96                 return -ENOMEM;
  97         }
  98         *hash_table = hash_tbl;
  99         /* allocate the memory for the hash key table */
 100         hash_tbl->num_key_entries = cparams->num_key_entries;
 101         hash_tbl->key_tbl.data_size = cparams->key_size;
 102         hash_tbl->key_tbl.mem_size = cparams->key_size *
 103                 (cparams->num_key_entries + 1);
 104         hash_tbl->key_tbl.key_data = rte_zmalloc("Generic hash keys",
 105                                                  hash_tbl->key_tbl.mem_size, 0);
 106         if (!hash_tbl->key_tbl.key_data) {
 107                 BNXT_TF_DBG(ERR, "failed to alloc mem for hash key\n");
 108                 rc = -ENOMEM;
 109                 goto init_error;
 110         }
 111
 112         /* allocate the memory for the hash table */
 113         hash_tbl->hash_bkt_num = cparams->num_buckets / ULP_HASH_BUCKET_ROW_SZ;
 114         hash_tbl->hash_tbl_size = cparams->num_hash_tbl_entries;
 115         size = hash_tbl->hash_tbl_size * hash_tbl->hash_bkt_num *
 116                 sizeof(struct ulp_hash_bucket_entry);
 117         hash_tbl->hash_list = rte_zmalloc("Generic hash table list", size,
 118                                           ULP_BUFFER_ALIGN_64_BYTE);
 119         if (!hash_tbl->hash_list) {
 120                 BNXT_TF_DBG(ERR, "failed to alloc mem for hash tbl\n");
 121                 rc = -ENOMEM;
 122                 goto init_error;
 123         }
 124
 125         /* calculate the hash_mask based on the tbl size */
 126         size = 1;
 127         while (size < hash_tbl->hash_tbl_size)
 128                 size = size << 1;
 129         hash_tbl->hash_mask = size - 1;
 130
 131         /* allocate the memory for the bit allocator */
 132         size = (cparams->num_key_entries / sizeof(uint64_t));
 133         size = ULP_BYTE_ROUND_OFF_8(size);
 134         hash_tbl->bit_list.bsize = size;
 135         hash_tbl->bit_list.bdata = rte_zmalloc("Generic hash bit alloc", size,
 136                                                ULP_BUFFER_ALIGN_64_BYTE);
 137         if (!hash_tbl->bit_list.bdata) {
 138                 BNXT_TF_DBG(ERR, "failed to alloc mem for hash bit list\n");
 139                 rc = -ENOMEM;
 140                 goto init_error;
 141         }
 142         return rc;
 143
 144 init_error:
 145         if (hash_tbl)
 146                 ulp_gen_hash_tbl_list_deinit(hash_tbl);
 147         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 ulp_gen_hash_tbl_list_deinit(struct ulp_gen_hash_tbl *hash_tbl)
 159 {
 160         if (!hash_tbl)
 161                 return -EINVAL;
 162
 163         if (hash_tbl->key_tbl.key_data) {
 164                 rte_free(hash_tbl->key_tbl.key_data);
 165                 hash_tbl->key_tbl.key_data = NULL;
 166         }
 167
 168         if (hash_tbl->hash_list) {
 169                 rte_free(hash_tbl->hash_list);
 170                 hash_tbl->hash_list = NULL;
 171         }
 172
 173         if (hash_tbl->bit_list.bdata) {
 174                 rte_free(hash_tbl->bit_list.bdata);
 175                 hash_tbl->bit_list.bdata = NULL;
 176         }
 177
 178         rte_free(hash_tbl);
 179         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 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         if (!hash_tbl || !entry || !entry->key_data || entry->key_length !=
 200             hash_tbl->key_tbl.data_size) {
 201                 BNXT_TF_DBG(ERR, "invalid arguments\n");
 202                 return -EINVAL;
 203         }
 204
 205         /* calculate the hash */
 206         hash_id = tf_hash_calc_crc32(entry->key_data,
 207                                      hash_tbl->key_tbl.data_size);
 208         hash_id = (uint16_t)(((hash_id >> 16) & 0xffff) ^ (hash_id & 0xffff));
 209         hash_id &= hash_tbl->hash_mask;
 210         hash_id = hash_id * hash_tbl->hash_bkt_num;
 211
 212         /* Iterate the bucket list */
 213         bucket = (uint16_t *)&hash_tbl->hash_list[hash_id];
 214         for (idx = 0; idx < (hash_tbl->hash_bkt_num * ULP_HASH_BUCKET_ROW_SZ);
 215               idx++, bucket++) {
 216                 if (ULP_HASH_BUCKET_INUSE(bucket)) {
 217                         /* compare the key contents */
 218                         key_idx = ULP_HASH_BUCKET_INDEX(bucket);
 219                         if (key_idx >= hash_tbl->num_key_entries) {
 220                                 BNXT_TF_DBG(ERR, "Hash table corruption\n");
 221                                 return -EINVAL;
 222                         }
 223                         if (!memcmp(entry->key_data,
 224                                     &hash_tbl->key_tbl.key_data[key_idx *
 225                                     hash_tbl->key_tbl.data_size],
 226                                     hash_tbl->key_tbl.data_size)) {
 227                                 /* Found the entry */
 228                                 entry->search_flag = ULP_GEN_HASH_SEARCH_FOUND;
 229                                 entry->hash_index = ULP_HASH_INDEX_CALC(hash_id,
 230                                                                         idx);
 231                                 entry->key_idx = key_idx;
 232                                 return 0;
 233                         }
 234                 } else if (miss_idx == ULP_HASH_BUCKET_INVAL) {
 235                         miss_idx = idx;
 236                 }
 237         }
 238
 239         if (miss_idx == ULP_HASH_BUCKET_INVAL) {
 240                 entry->search_flag = ULP_GEN_HASH_SEARCH_FULL;
 241         } else {
 242                 entry->search_flag = ULP_GEN_HASH_SEARCH_MISSED;
 243                 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 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         if (!hash_tbl || !entry) {
 265                 BNXT_TF_DBG(ERR, "invalid arguments\n");
 266                 return -EINVAL;
 267         }
 268
 269         idx = ULP_HASH_GET_H_INDEX(entry->hash_index);
 270         if (idx > (hash_tbl->hash_tbl_size * hash_tbl->hash_bkt_num)) {
 271                 BNXT_TF_DBG(ERR, "invalid hash index %x\n", idx);
 272                 return -EINVAL;
 273         }
 274         bucket = (uint16_t *)&hash_tbl->hash_list[idx];
 275         idx  = ULP_HASH_GET_B_INDEX(entry->hash_index);
 276         if (idx >= (hash_tbl->hash_bkt_num * ULP_HASH_BUCKET_ROW_SZ)) {
 277                 BNXT_TF_DBG(ERR, "invalid bucket index %x\n", idx);
 278                 return -EINVAL;
 279         }
 280         bucket += idx;
 281         if (ULP_HASH_BUCKET_INUSE(bucket)) {
 282                 entry->key_idx = ULP_HASH_BUCKET_INDEX(bucket);
 283                 entry->search_flag = ULP_GEN_HASH_SEARCH_FOUND;
 284         } else {
 285                 entry->search_flag = ULP_GEN_HASH_SEARCH_MISSED;
 286                 return -ENOENT;
 287         }
 288         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 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         idx = ULP_HASH_GET_H_INDEX(entry->hash_index);
 311         bucket = (uint16_t *)&hash_tbl->hash_list[idx];
 312         bucket += ULP_HASH_GET_B_INDEX(entry->hash_index);
 313         if (ulp_bit_alloc_list_alloc(&hash_tbl->bit_list, &key_index)) {
 314                 BNXT_TF_DBG(ERR, "Error in bit list alloc\n");
 315                 return -ENOMEM;
 316         }
 317         if (key_index > hash_tbl->num_key_entries) {
 318                 BNXT_TF_DBG(ERR, "reached max size %u:%u\n", key_index,
 319                             hash_tbl->num_key_entries);
 320                 ulp_bit_alloc_list_dealloc(&hash_tbl->bit_list, key_index);
 321                 return -ENOMEM;
 322         }
 323         /* Update the hash entry */
 324         ULP_HASH_BUCKET_MARK_INUSE(bucket, (uint16_t)key_index);
 325
 326         /* update the hash key and key index */
 327         entry->key_idx = key_index;
 328         key_index = key_index * hash_tbl->key_tbl.data_size;
 329         memcpy(&hash_tbl->key_tbl.key_data[key_index], entry->key_data,
 330                hash_tbl->key_tbl.data_size);
 331
 332         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 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         idx = ULP_HASH_GET_H_INDEX(entry->hash_index);
 353         bucket = (uint16_t *)&hash_tbl->hash_list[idx];
 354         bucket += ULP_HASH_GET_B_INDEX(entry->hash_index);
 355
 356         /* Get the hash entry */
 357         key_index = ULP_HASH_BUCKET_INDEX(bucket);
 358         if (key_index >= hash_tbl->num_key_entries) {
 359                 BNXT_TF_DBG(ERR, "Hash table corruption\n");
 360                 return -EINVAL;
 361         }
 362
 363         /* reset the bit in the bit allocator */
 364         if (ulp_bit_alloc_list_dealloc(&hash_tbl->bit_list,
 365                                        key_index)) {
 366                 BNXT_TF_DBG(ERR, "Error is bit list dealloc\n");
 367                 return -EINVAL;
 368         }
 369
 370         /* erase key details and bucket details */
 371         key_index = key_index * hash_tbl->key_tbl.data_size;
 372         memset(&hash_tbl->key_tbl.key_data[key_index], 0,
 373                hash_tbl->key_tbl.data_size);
 374         ULP_HASH_BUCKET_CLEAR(bucket);
 375
 376         return 0;
 377 }