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