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
ulp_bit_alloc_list_alloc(struct bit_alloc_list * blist,uint32_t * index)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
ulp_bit_alloc_list_dealloc(struct bit_alloc_list * blist,uint32_t index)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
ulp_gen_hash_tbl_list_init(struct ulp_hash_create_params * cparams,struct ulp_gen_hash_tbl ** hash_table)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
ulp_gen_hash_tbl_list_deinit(struct ulp_gen_hash_tbl * hash_tbl)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
ulp_gen_hash_tbl_list_key_search(struct ulp_gen_hash_tbl * hash_tbl,struct ulp_gen_hash_entry_params * entry)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
ulp_gen_hash_tbl_list_index_search(struct ulp_gen_hash_tbl * hash_tbl,struct ulp_gen_hash_entry_params * entry)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
ulp_gen_hash_tbl_list_add(struct ulp_gen_hash_tbl * hash_tbl,struct ulp_gen_hash_entry_params * entry)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
ulp_gen_hash_tbl_list_del(struct ulp_gen_hash_tbl * hash_tbl,struct ulp_gen_hash_entry_params * entry)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