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 } 378