Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2014-2023 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 : 0 : 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 : 0 : uint32_t bsize_64 = blist->bsize / ULP_64B_IN_BYTES;
20 : :
21 : : /* Iterate all numbers that have all 1's */
22 : : do {
23 : 0 : bentry = blist->bdata[idx++];
24 [ # # ]: 0 : } while (bentry == -1UL && idx <= bsize_64);
25 : :
26 [ # # ]: 0 : if (idx <= bsize_64) {
27 [ # # ]: 0 : if (bentry)
28 : 0 : jdx = __builtin_clzl(~bentry);
29 : 0 : *index = ((idx - 1) * ULP_INDEX_BITMAP_SIZE) + jdx;
30 : 0 : ULP_INDEX_BITMAP_SET(blist->bdata[(idx - 1)], jdx);
31 : 0 : return 0;
32 : : }
33 : 0 : jdx = (uint32_t)(bsize_64 * ULP_INDEX_BITMAP_SIZE);
34 : 0 : BNXT_TF_DBG(ERR, "bit allocator is full reached max:%x\n", jdx);
35 : 0 : return -1;
36 : : }
37 : :
38 : : static
39 : 0 : int32_t ulp_bit_alloc_list_dealloc(struct bit_alloc_list *blist,
40 : : uint32_t index)
41 : : {
42 : : uint32_t idx = 0, jdx;
43 : 0 : uint32_t bsize_64 = blist->bsize / ULP_64B_IN_BYTES;
44 : :
45 : 0 : idx = index / ULP_INDEX_BITMAP_SIZE;
46 [ # # ]: 0 : if (idx >= bsize_64) {
47 : 0 : BNXT_TF_DBG(ERR, "invalid bit index %x:%x\n", idx,
48 : : blist->bsize);
49 : 0 : return -EINVAL;
50 : : }
51 : : jdx = index % ULP_INDEX_BITMAP_SIZE;
52 : 0 : ULP_INDEX_BITMAP_RESET(blist->bdata[idx], jdx);
53 : 0 : 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 : 0 : 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 [ # # ]: 0 : if (!hash_table || !cparams) {
74 : 0 : BNXT_TF_DBG(ERR, "invalid arguments\n");
75 : 0 : return -EINVAL;
76 : : }
77 : :
78 : : /* validate the size parameters */
79 [ # # # # ]: 0 : if (ulp_util_is_power_of_2(cparams->num_hash_tbl_entries) ||
80 : 0 : ulp_util_is_power_of_2(cparams->num_key_entries) ||
81 [ # # ]: 0 : (cparams->num_buckets % ULP_HASH_BUCKET_ROW_SZ)) {
82 : 0 : BNXT_TF_DBG(ERR, "invalid arguments for hash tbl\n");
83 : 0 : return -EINVAL;
84 : : }
85 : :
86 : : /* validate the size of the hash table size */
87 [ # # ]: 0 : if (cparams->num_hash_tbl_entries >= ULP_GEN_HASH_MAX_TBL_SIZE) {
88 : 0 : BNXT_TF_DBG(ERR, "invalid size for hash tbl\n");
89 : 0 : return -EINVAL;
90 : : }
91 : :
92 : 0 : hash_tbl = rte_zmalloc("Generic hash table",
93 : : sizeof(struct ulp_gen_hash_tbl), 0);
94 [ # # ]: 0 : if (!hash_tbl) {
95 : 0 : BNXT_TF_DBG(ERR, "failed to alloc mem for hash tbl\n");
96 : 0 : return -ENOMEM;
97 : : }
98 : 0 : *hash_table = hash_tbl;
99 : : /* allocate the memory for the hash key table */
100 : 0 : hash_tbl->num_key_entries = cparams->num_key_entries;
101 : 0 : hash_tbl->key_tbl.data_size = cparams->key_size;
102 : 0 : hash_tbl->key_tbl.mem_size = cparams->key_size *
103 : 0 : (cparams->num_key_entries + 1);
104 : 0 : hash_tbl->key_tbl.key_data = rte_zmalloc("Generic hash keys",
105 : : hash_tbl->key_tbl.mem_size, 0);
106 [ # # ]: 0 : if (!hash_tbl->key_tbl.key_data) {
107 : 0 : BNXT_TF_DBG(ERR, "failed to alloc mem for hash key\n");
108 : : rc = -ENOMEM;
109 : 0 : goto init_error;
110 : : }
111 : :
112 : : /* allocate the memory for the hash table */
113 : 0 : hash_tbl->hash_bkt_num = cparams->num_buckets / ULP_HASH_BUCKET_ROW_SZ;
114 : 0 : hash_tbl->hash_tbl_size = cparams->num_hash_tbl_entries;
115 : 0 : size = hash_tbl->hash_tbl_size * hash_tbl->hash_bkt_num *
116 : : sizeof(struct ulp_hash_bucket_entry);
117 : 0 : hash_tbl->hash_list = rte_zmalloc("Generic hash table list", size,
118 : : ULP_BUFFER_ALIGN_64_BYTE);
119 [ # # ]: 0 : if (!hash_tbl->hash_list) {
120 : 0 : BNXT_TF_DBG(ERR, "failed to alloc mem for hash tbl\n");
121 : : rc = -ENOMEM;
122 : 0 : goto init_error;
123 : : }
124 : :
125 : : /* calculate the hash_mask based on the tbl size */
126 : : size = 1;
127 [ # # ]: 0 : while (size < hash_tbl->hash_tbl_size)
128 : 0 : size = size << 1;
129 : 0 : hash_tbl->hash_mask = size - 1;
130 : :
131 : : /* allocate the memory for the bit allocator */
132 : 0 : size = (cparams->num_key_entries / sizeof(uint64_t));
133 : 0 : size = ULP_BYTE_ROUND_OFF_8(size);
134 : 0 : hash_tbl->bit_list.bsize = size;
135 : 0 : hash_tbl->bit_list.bdata = rte_zmalloc("Generic hash bit alloc", size,
136 : : ULP_BUFFER_ALIGN_64_BYTE);
137 [ # # ]: 0 : if (!hash_tbl->bit_list.bdata) {
138 : 0 : BNXT_TF_DBG(ERR, "failed to alloc mem for hash bit list\n");
139 : : rc = -ENOMEM;
140 : 0 : goto init_error;
141 : : }
142 : : return rc;
143 : :
144 : 0 : init_error:
145 : : if (hash_tbl)
146 : 0 : ulp_gen_hash_tbl_list_deinit(hash_tbl);
147 : 0 : 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 : 0 : ulp_gen_hash_tbl_list_deinit(struct ulp_gen_hash_tbl *hash_tbl)
159 : : {
160 [ # # ]: 0 : if (!hash_tbl)
161 : : return -EINVAL;
162 : :
163 [ # # ]: 0 : if (hash_tbl->key_tbl.key_data) {
164 : 0 : rte_free(hash_tbl->key_tbl.key_data);
165 : 0 : hash_tbl->key_tbl.key_data = NULL;
166 : : }
167 : :
168 [ # # ]: 0 : if (hash_tbl->hash_list) {
169 : 0 : rte_free(hash_tbl->hash_list);
170 : 0 : hash_tbl->hash_list = NULL;
171 : : }
172 : :
173 [ # # ]: 0 : if (hash_tbl->bit_list.bdata) {
174 : 0 : rte_free(hash_tbl->bit_list.bdata);
175 : 0 : hash_tbl->bit_list.bdata = NULL;
176 : : }
177 : :
178 : 0 : rte_free(hash_tbl);
179 : 0 : 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 : 0 : 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 [ # # # # ]: 0 : if (!hash_tbl || !entry || !entry->key_data || entry->key_length !=
200 [ # # ]: 0 : hash_tbl->key_tbl.data_size) {
201 : 0 : BNXT_TF_DBG(ERR, "invalid arguments\n");
202 : 0 : return -EINVAL;
203 : : }
204 : :
205 : : /* calculate the hash */
206 : 0 : hash_id = tf_hash_calc_crc32(entry->key_data,
207 : : hash_tbl->key_tbl.data_size);
208 : 0 : hash_id = (uint16_t)(((hash_id >> 16) & 0xffff) ^ (hash_id & 0xffff));
209 : 0 : hash_id &= hash_tbl->hash_mask;
210 : 0 : hash_id = hash_id * hash_tbl->hash_bkt_num;
211 : :
212 : : /* Iterate the bucket list */
213 : 0 : bucket = (uint16_t *)&hash_tbl->hash_list[hash_id];
214 [ # # ]: 0 : for (idx = 0; idx < (hash_tbl->hash_bkt_num * ULP_HASH_BUCKET_ROW_SZ);
215 : 0 : idx++, bucket++) {
216 [ # # ]: 0 : if (ULP_HASH_BUCKET_INUSE(bucket)) {
217 : : /* compare the key contents */
218 : 0 : key_idx = ULP_HASH_BUCKET_INDEX(bucket);
219 [ # # ]: 0 : if (key_idx >= hash_tbl->num_key_entries) {
220 : 0 : BNXT_TF_DBG(ERR, "Hash table corruption\n");
221 : 0 : return -EINVAL;
222 : : }
223 : 0 : if (!memcmp(entry->key_data,
224 : 0 : &hash_tbl->key_tbl.key_data[key_idx *
225 : : hash_tbl->key_tbl.data_size],
226 [ # # ]: 0 : hash_tbl->key_tbl.data_size)) {
227 : : /* Found the entry */
228 : 0 : entry->search_flag = ULP_GEN_HASH_SEARCH_FOUND;
229 : 0 : entry->hash_index = ULP_HASH_INDEX_CALC(hash_id,
230 : : idx);
231 : 0 : entry->key_idx = key_idx;
232 : 0 : return 0;
233 : : }
234 [ # # ]: 0 : } else if (miss_idx == ULP_HASH_BUCKET_INVAL) {
235 : 0 : miss_idx = idx;
236 : : }
237 : : }
238 : :
239 [ # # ]: 0 : if (miss_idx == ULP_HASH_BUCKET_INVAL) {
240 : 0 : entry->search_flag = ULP_GEN_HASH_SEARCH_FULL;
241 : : } else {
242 : 0 : entry->search_flag = ULP_GEN_HASH_SEARCH_MISSED;
243 : 0 : 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 : 0 : 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 [ # # ]: 0 : if (!hash_tbl || !entry) {
265 : 0 : BNXT_TF_DBG(ERR, "invalid arguments\n");
266 : 0 : return -EINVAL;
267 : : }
268 : :
269 : 0 : idx = ULP_HASH_GET_H_INDEX(entry->hash_index);
270 [ # # ]: 0 : if (idx > (hash_tbl->hash_tbl_size * hash_tbl->hash_bkt_num)) {
271 : 0 : BNXT_TF_DBG(ERR, "invalid hash index %x\n", idx);
272 : 0 : return -EINVAL;
273 : : }
274 : 0 : bucket = (uint16_t *)&hash_tbl->hash_list[idx];
275 : 0 : idx = ULP_HASH_GET_B_INDEX(entry->hash_index);
276 [ # # ]: 0 : if (idx >= (hash_tbl->hash_bkt_num * ULP_HASH_BUCKET_ROW_SZ)) {
277 : 0 : BNXT_TF_DBG(ERR, "invalid bucket index %x\n", idx);
278 : 0 : return -EINVAL;
279 : : }
280 : 0 : bucket += idx;
281 [ # # ]: 0 : if (ULP_HASH_BUCKET_INUSE(bucket)) {
282 : 0 : entry->key_idx = ULP_HASH_BUCKET_INDEX(bucket);
283 : 0 : entry->search_flag = ULP_GEN_HASH_SEARCH_FOUND;
284 : : } else {
285 : 0 : entry->search_flag = ULP_GEN_HASH_SEARCH_MISSED;
286 : 0 : return -ENOENT;
287 : : }
288 : 0 : 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 : 0 : 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 : 0 : idx = ULP_HASH_GET_H_INDEX(entry->hash_index);
311 : 0 : bucket = (uint16_t *)&hash_tbl->hash_list[idx];
312 : 0 : bucket += ULP_HASH_GET_B_INDEX(entry->hash_index);
313 [ # # ]: 0 : if (ulp_bit_alloc_list_alloc(&hash_tbl->bit_list, &key_index)) {
314 : 0 : BNXT_TF_DBG(ERR, "Error in bit list alloc\n");
315 : 0 : return -ENOMEM;
316 : : }
317 [ # # ]: 0 : if (key_index > hash_tbl->num_key_entries) {
318 : 0 : BNXT_TF_DBG(ERR, "reached max size %u:%u\n", key_index,
319 : : hash_tbl->num_key_entries);
320 : 0 : ulp_bit_alloc_list_dealloc(&hash_tbl->bit_list, key_index);
321 : 0 : return -ENOMEM;
322 : : }
323 : : /* Update the hash entry */
324 : 0 : ULP_HASH_BUCKET_MARK_INUSE(bucket, (uint16_t)key_index);
325 : :
326 : : /* update the hash key and key index */
327 : 0 : entry->key_idx = key_index;
328 : 0 : key_index = key_index * hash_tbl->key_tbl.data_size;
329 : 0 : memcpy(&hash_tbl->key_tbl.key_data[key_index], entry->key_data,
330 : : hash_tbl->key_tbl.data_size);
331 : :
332 : 0 : 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 : 0 : 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 : 0 : idx = ULP_HASH_GET_H_INDEX(entry->hash_index);
353 : 0 : bucket = (uint16_t *)&hash_tbl->hash_list[idx];
354 : 0 : bucket += ULP_HASH_GET_B_INDEX(entry->hash_index);
355 : :
356 : : /* Get the hash entry */
357 : 0 : key_index = ULP_HASH_BUCKET_INDEX(bucket);
358 [ # # ]: 0 : if (key_index >= hash_tbl->num_key_entries) {
359 : 0 : BNXT_TF_DBG(ERR, "Hash table corruption\n");
360 : 0 : return -EINVAL;
361 : : }
362 : :
363 : : /* reset the bit in the bit allocator */
364 [ # # ]: 0 : if (ulp_bit_alloc_list_dealloc(&hash_tbl->bit_list,
365 : : key_index)) {
366 : 0 : BNXT_TF_DBG(ERR, "Error is bit list dealloc\n");
367 : 0 : return -EINVAL;
368 : : }
369 : :
370 : : /* erase key details and bucket details */
371 : 0 : key_index = key_index * hash_tbl->key_tbl.data_size;
372 : 0 : memset(&hash_tbl->key_tbl.key_data[key_index], 0,
373 : : hash_tbl->key_tbl.data_size);
374 : 0 : ULP_HASH_BUCKET_CLEAR(bucket);
375 : :
376 : 0 : return 0;
377 : : }
|