1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2014-2021 Broadcom
7 #include <rte_malloc.h>
8 #include "bnxt_tf_common.h"
9 #include "ulp_gen_hash.h"
10 #include "ulp_utils.h"
14 int32_t ulp_bit_alloc_list_alloc(struct bit_alloc_list *blist,
18 uint32_t idx = 0, jdx = 0;
19 uint32_t bsize_64 = blist->bsize / ULP_64B_IN_BYTES;
21 /* Iterate all numbers that have all 1's */
23 bentry = blist->bdata[idx++];
24 } while (bentry == -1UL && idx <= bsize_64);
26 if (idx <= bsize_64) {
28 jdx = __builtin_clzl(~bentry);
29 *index = ((idx - 1) * ULP_INDEX_BITMAP_SIZE) + jdx;
30 ULP_INDEX_BITMAP_SET(blist->bdata[(idx - 1)], jdx);
33 jdx = (uint32_t)(bsize_64 * ULP_INDEX_BITMAP_SIZE);
34 BNXT_TF_DBG(ERR, "bit allocator is full reached max:%x\n", jdx);
39 int32_t ulp_bit_alloc_list_dealloc(struct bit_alloc_list *blist,
42 uint32_t idx = 0, jdx;
43 uint32_t bsize_64 = blist->bsize / ULP_64B_IN_BYTES;
45 idx = index / ULP_INDEX_BITMAP_SIZE;
46 if (idx >= bsize_64) {
47 BNXT_TF_DBG(ERR, "invalid bit index %x:%x\n", idx,
51 jdx = index % ULP_INDEX_BITMAP_SIZE;
52 ULP_INDEX_BITMAP_RESET(blist->bdata[idx], jdx);
57 * Initialize the Generic Hash table
59 * cparams [in] Pointer to hash create params list
60 * hash_tbl [out] the pointer to created hash table
62 * returns 0 on success
65 ulp_gen_hash_tbl_list_init(struct ulp_hash_create_params *cparams,
66 struct ulp_gen_hash_tbl **hash_table)
68 struct ulp_gen_hash_tbl *hash_tbl = NULL;
72 /* validate the arguments */
73 if (!hash_table || !cparams) {
74 BNXT_TF_DBG(ERR, "invalid arguments\n");
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");
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");
92 hash_tbl = rte_zmalloc("Generic hash table",
93 sizeof(struct ulp_gen_hash_tbl), 0);
95 BNXT_TF_DBG(ERR, "failed to alloc mem for hash tbl\n");
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");
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");
125 /* calculate the hash_mask based on the tbl size */
127 while (size < hash_tbl->hash_tbl_size)
129 hash_tbl->hash_mask = size - 1;
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");
146 ulp_gen_hash_tbl_list_deinit(hash_tbl);
151 * Free the generic hash table
153 * hash_tbl [in] the pointer to hash table
155 * returns 0 on success
158 ulp_gen_hash_tbl_list_deinit(struct ulp_gen_hash_tbl *hash_tbl)
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;
168 if (hash_tbl->hash_list) {
169 rte_free(hash_tbl->hash_list);
170 hash_tbl->hash_list = NULL;
173 if (hash_tbl->bit_list.bdata) {
174 rte_free(hash_tbl->bit_list.bdata);
175 hash_tbl->bit_list.bdata = NULL;
183 * Search the generic hash table using key data
185 * hash_tbl [in] the pointer to hash table
186 * entry [in/out] pointer to hash entry details.
188 * returns 0 on success and marks search flag as found.
191 ulp_gen_hash_tbl_list_key_search(struct ulp_gen_hash_tbl *hash_tbl,
192 struct ulp_gen_hash_entry_params *entry)
194 uint32_t hash_id, key_idx, idx;
196 int32_t miss_idx = ULP_HASH_BUCKET_INVAL;
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");
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;
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);
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");
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,
231 entry->key_idx = key_idx;
234 } else if (miss_idx == ULP_HASH_BUCKET_INVAL) {
239 if (miss_idx == ULP_HASH_BUCKET_INVAL) {
240 entry->search_flag = ULP_GEN_HASH_SEARCH_FULL;
242 entry->search_flag = ULP_GEN_HASH_SEARCH_MISSED;
243 entry->hash_index = ULP_HASH_INDEX_CALC(hash_id, miss_idx);
249 * Search the generic hash table using hash index
251 * hash_tbl [in] the pointer to hash table
252 * entry [in/out] pointer to hash entry details.
254 * returns 0 on success and marks search flag as found.
257 ulp_gen_hash_tbl_list_index_search(struct ulp_gen_hash_tbl *hash_tbl,
258 struct ulp_gen_hash_entry_params *entry)
263 /* validate the arguments */
264 if (!hash_tbl || !entry) {
265 BNXT_TF_DBG(ERR, "invalid arguments\n");
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);
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);
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;
285 entry->search_flag = ULP_GEN_HASH_SEARCH_MISSED;
292 * Add the entry to the generic hash table
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.
298 * returns 0 on success
302 ulp_gen_hash_tbl_list_add(struct ulp_gen_hash_tbl *hash_tbl,
303 struct ulp_gen_hash_entry_params *entry)
307 uint32_t idx, key_index;
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");
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);
323 /* Update the hash entry */
324 ULP_HASH_BUCKET_MARK_INUSE(bucket, (uint16_t)key_index);
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);
336 * Delete the entry in the generic hash table
338 * hash_tbl [in] the pointer to hash table
339 * entry [in] pointer to hash entry details. Fill the hash index details to be
342 * returns 0 on success
345 ulp_gen_hash_tbl_list_del(struct ulp_gen_hash_tbl *hash_tbl,
346 struct ulp_gen_hash_entry_params *entry)
349 uint32_t idx, key_index;
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);
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");
363 /* reset the bit in the bit allocator */
364 if (ulp_bit_alloc_list_dealloc(&hash_tbl->bit_list,
366 BNXT_TF_DBG(ERR, "Error is bit list dealloc\n");
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);