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