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;
20 /* Iterate all numbers that have all 1's */
22 bentry = blist->bdata[idx++];
23 } while (bentry == -1UL && idx < blist->bsize);
25 if (idx < blist->bsize) {
27 jdx = __builtin_clzl(~bentry);
28 *index = ((idx - 1) * ULP_INDEX_BITMAP_SIZE) + jdx;
29 ULP_INDEX_BITMAP_SET(blist->bdata[(idx - 1)], jdx);
32 jdx = (uint32_t)(blist->bsize * ULP_INDEX_BITMAP_SIZE);
33 BNXT_TF_DBG(ERR, "bit allocator is full reached max:%x\n", jdx);
38 int32_t ulp_bit_alloc_list_dealloc(struct bit_alloc_list *blist,
41 uint32_t idx = 0, jdx;
43 idx = index / ULP_INDEX_BITMAP_SIZE;
44 if (idx >= blist->bsize) {
45 BNXT_TF_DBG(ERR, "invalid bit index %x:%x\n", idx,
49 jdx = index % ULP_INDEX_BITMAP_SIZE;
50 ULP_INDEX_BITMAP_RESET(blist->bdata[idx], jdx);
55 * Initialize the Generic Hash table
57 * cparams [in] Pointer to hash create params list
58 * hash_tbl [out] the pointer to created hash table
60 * returns 0 on success
63 ulp_gen_hash_tbl_list_init(struct ulp_hash_create_params *cparams,
64 struct ulp_gen_hash_tbl **hash_table)
66 struct ulp_gen_hash_tbl *hash_tbl = NULL;
70 /* validate the arguments */
71 if (!hash_table || !cparams) {
72 BNXT_TF_DBG(ERR, "invalid arguments\n");
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");
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");
90 hash_tbl = rte_zmalloc("Generic hash table",
91 sizeof(struct ulp_gen_hash_tbl), 0);
93 BNXT_TF_DBG(ERR, "failed to alloc mem for hash tbl\n");
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");
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");
123 /* calculate the hash_mask based on the tbl size */
125 while (size < hash_tbl->hash_tbl_size)
127 hash_tbl->hash_mask = size - 1;
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");
143 ulp_gen_hash_tbl_list_deinit(hash_tbl);
148 * Free the generic hash table
150 * hash_tbl [in] the pointer to hash table
152 * returns 0 on success
155 ulp_gen_hash_tbl_list_deinit(struct ulp_gen_hash_tbl *hash_tbl)
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;
165 if (hash_tbl->hash_list) {
166 rte_free(hash_tbl->hash_list);
167 hash_tbl->hash_list = NULL;
170 if (hash_tbl->bit_list.bdata) {
171 rte_free(hash_tbl->bit_list.bdata);
172 hash_tbl->bit_list.bdata = NULL;
180 * Search the generic hash table using key data
182 * hash_tbl [in] the pointer to hash table
183 * entry [in/out] pointer to hash entry details.
185 * returns 0 on success and marks search flag as found.
188 ulp_gen_hash_tbl_list_key_search(struct ulp_gen_hash_tbl *hash_tbl,
189 struct ulp_gen_hash_entry_params *entry)
191 uint32_t hash_id, key_idx, idx;
193 int32_t miss_idx = ULP_HASH_BUCKET_INVAL;
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");
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;
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);
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");
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,
228 entry->key_idx = key_idx;
231 } else if (miss_idx == ULP_HASH_BUCKET_INVAL) {
236 if (miss_idx == ULP_HASH_BUCKET_INVAL) {
237 entry->search_flag = ULP_GEN_HASH_SEARCH_FULL;
239 entry->search_flag = ULP_GEN_HASH_SEARCH_MISSED;
240 entry->hash_index = ULP_HASH_INDEX_CALC(hash_id, miss_idx);
246 * Search the generic hash table using hash index
248 * hash_tbl [in] the pointer to hash table
249 * entry [in/out] pointer to hash entry details.
251 * returns 0 on success and marks search flag as found.
254 ulp_gen_hash_tbl_list_index_search(struct ulp_gen_hash_tbl *hash_tbl,
255 struct ulp_gen_hash_entry_params *entry)
260 /* validate the arguments */
261 if (!hash_tbl || !entry) {
262 BNXT_TF_DBG(ERR, "invalid arguments\n");
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);
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);
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;
282 entry->search_flag = ULP_GEN_HASH_SEARCH_MISSED;
289 * Add the entry to the generic hash table
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.
295 * returns 0 on success
299 ulp_gen_hash_tbl_list_add(struct ulp_gen_hash_tbl *hash_tbl,
300 struct ulp_gen_hash_entry_params *entry)
304 uint32_t idx, key_index;
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");
315 /* Update the hash entry */
316 ULP_HASH_BUCKET_MARK_INUSE(bucket, (uint16_t)key_index);
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);
328 * Delete the entry in the generic hash table
330 * hash_tbl [in] the pointer to hash table
331 * entry [in] pointer to hash entry details. Fill the hash index details to be
334 * returns 0 on success
337 ulp_gen_hash_tbl_list_del(struct ulp_gen_hash_tbl *hash_tbl,
338 struct ulp_gen_hash_entry_params *entry)
341 uint32_t idx, key_index;
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);
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");
355 /* reset the bit in the bit allocator */
356 if (ulp_bit_alloc_list_dealloc(&hash_tbl->bit_list,
358 BNXT_TF_DBG(ERR, "Error is bit list dealloc\n");
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);