net/ice/base: init boost TCAM table for parser
[dpdk.git] / drivers / net / bnxt / tf_core / dpool.c
1 /* SPDX-License-Identifier: BSD-3-Clause
2  * Copyright(c) 2019-2021 Broadcom
3  * All rights reserved.
4  */
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <stdbool.h>
8 #include <stdint.h>
9 #include <errno.h>
10
11 #include <rte_malloc.h>
12
13 #include "tfp.h"
14 #include "dpool.h"
15
16 int dpool_init(struct dpool *dpool,
17                uint32_t start_index,
18                uint32_t size,
19                uint8_t max_alloc_size,
20                void *user_data,
21                int (*move_callback)(void *, uint64_t, uint32_t))
22 {
23         uint32_t i;
24         int rc;
25         struct tfp_calloc_parms parms;
26
27         parms.nitems = size;
28         parms.size = sizeof(struct dpool_entry);
29         parms.alignment = 0;
30
31         rc = tfp_calloc(&parms);
32
33         if (rc)
34                 return rc;
35
36         dpool->entry = parms.mem_va;
37         dpool->start_index = start_index;
38         dpool->size = size;
39         dpool->max_alloc_size = max_alloc_size;
40         dpool->user_data = user_data;
41         dpool->move_callback = move_callback;
42         /*
43          * Init entries
44          */
45         for (i = 0; i < size; i++) {
46                 dpool->entry[i].flags = 0;
47                 dpool->entry[i].index = start_index;
48                 dpool->entry[i].entry_data = 0UL;
49                 start_index++;
50         }
51
52         return 0;
53 }
54
55 static int dpool_move(struct dpool *dpool,
56                       uint32_t dst_index,
57                       uint32_t src_index)
58 {
59         uint32_t size;
60         uint32_t i;
61         if (DP_IS_FREE(dpool->entry[dst_index].flags)) {
62                 size = DP_FLAGS_SIZE(dpool->entry[src_index].flags);
63
64                 dpool->entry[dst_index].flags = dpool->entry[src_index].flags;
65                 dpool->entry[dst_index].entry_data = dpool->entry[src_index].entry_data;
66
67                 if (dpool->move_callback != NULL) {
68                         dpool->move_callback(dpool->user_data,
69                                              dpool->entry[src_index].entry_data,
70                                              dst_index + dpool->start_index);
71                 }
72
73                 dpool->entry[src_index].flags = 0;
74                 dpool->entry[src_index].entry_data = 0UL;
75
76                 for (i = 1; i < size; i++) {
77                         dpool->entry[dst_index + i].flags = size;
78                         dpool->entry[src_index + i].flags = 0;
79                 }
80         } else {
81                 return -1;
82         }
83
84         return 0;
85 }
86
87
88 int dpool_defrag(struct dpool *dpool,
89                  uint32_t entry_size,
90                  uint8_t defrag)
91 {
92         struct dpool_free_list *free_list;
93         struct dpool_adj_list *adj_list;
94         uint32_t count;
95         uint32_t index;
96         uint32_t used;
97         uint32_t i;
98         uint32_t size;
99         uint32_t largest_free_index = 0;
100         uint32_t largest_free_size;
101         uint32_t max;
102         uint32_t max_index;
103         uint32_t max_size = 0;
104         int rc;
105
106         free_list = rte_zmalloc("dpool_free_list",
107                                 sizeof(struct dpool_free_list), 0);
108         if (free_list == NULL) {
109                 TFP_DRV_LOG(ERR, "dpool free list allocation failed\n");
110                 return -ENOMEM;
111         }
112
113         adj_list = rte_zmalloc("dpool_adjacent_list",
114                                 sizeof(struct dpool_adj_list), 0);
115         if (adj_list == NULL) {
116                 TFP_DRV_LOG(ERR, "dpool adjacent list allocation failed\n");
117                 return -ENOMEM;
118         }
119
120         while (1) {
121                 /*
122                  * Create list of free entries
123                  */
124                 free_list->size = 0;
125                 largest_free_size = 0;
126                 largest_free_index = 0;
127                 count = 0;
128                 index = 0;
129
130                 for (i = 0; i < dpool->size; i++) {
131                         if (DP_IS_FREE(dpool->entry[i].flags)) {
132                                 if (count == 0)
133                                         index = i;
134                                 count++;
135                         } else if (count > 0) {
136                                 free_list->entry[free_list->size].index = index;
137                                 free_list->entry[free_list->size].size = count;
138
139                                 if (count > largest_free_size) {
140                                         largest_free_index = free_list->size;
141                                         largest_free_size = count;
142                                 }
143
144                                 free_list->size++;
145                                 count = 0;
146                         }
147                 }
148
149                 if (free_list->size == 0)
150                         largest_free_size = count;
151
152                 /*
153                  * If using defrag to fit and there's a large enough
154                  * space then we are done.
155                  */
156                 if (defrag == DP_DEFRAG_TO_FIT &&
157                     largest_free_size >= entry_size)
158                         goto done;
159
160                 /*
161                  * Create list of entries adjacent to free entries
162                  */
163                 count = 0;
164                 adj_list->size = 0;
165                 used = 0;
166
167                 for (i = 0; i < dpool->size; ) {
168                         if (DP_IS_USED(dpool->entry[i].flags)) {
169                                 used++;
170
171                                 if (count > 0) {
172                                         adj_list->entry[adj_list->size].index = i;
173                                         adj_list->entry[adj_list->size].size =
174                                                 DP_FLAGS_SIZE(dpool->entry[i].flags);
175                                         adj_list->entry[adj_list->size].left = count;
176
177                                         if (adj_list->size > 0 && used == 1)
178                                                 adj_list->entry[adj_list->size - 1].right = count;
179
180                                         adj_list->size++;
181                                 }
182
183                                 count = 0;
184                                 i += DP_FLAGS_SIZE(dpool->entry[i].flags);
185                         } else {
186                                 used = 0;
187                                 count++;
188                                 i++;
189                         }
190                 }
191
192                 /*
193                  * Using the size of the largest free space available
194                  * select the adjacency list entry of that size with
195                  * the largest left + right + size count. If there
196                  * are no entries of that size then decrement the size
197                  * and try again.
198                  */
199                 max = 0;
200                 max_index = 0;
201                 max_size = 0;
202
203                 for (size = largest_free_size; size > 0; size--) {
204                         for (i = 0; i < adj_list->size; i++) {
205                                 if (adj_list->entry[i].size == size &&
206                                     ((size +
207                                       adj_list->entry[i].left +
208                                       adj_list->entry[i].right) > max)) {
209                                         max = size +
210                                                 adj_list->entry[i].left +
211                                                 adj_list->entry[i].right;
212                                         max_size = size;
213                                         max_index = adj_list->entry[i].index;
214                                 }
215                         }
216
217                         if (max)
218                                 break;
219                 }
220
221                 /*
222                  * If the max entry is smaller than the largest_free_size
223                  * find the first entry in the free list that it cn fit in to.
224                  */
225                 if (max_size < largest_free_size) {
226                         for (i = 0; i < free_list->size; i++) {
227                                 if (free_list->entry[i].size >= max_size) {
228                                         largest_free_index = i;
229                                         break;
230                                 }
231                         }
232                 }
233
234                 /*
235                  * If we have a contender then move it to the new spot.
236                  */
237                 if (max) {
238                         rc = dpool_move(dpool,
239                                         free_list->entry[largest_free_index].index,
240                                         max_index);
241                         if (rc) {
242                                 rte_free(free_list);
243                                 rte_free(adj_list);
244                                 return rc;
245                         }
246                 } else {
247                         break;
248                 }
249         }
250
251 done:
252         rte_free(free_list);
253         rte_free(adj_list);
254         return largest_free_size;
255 }
256
257
258 uint32_t dpool_alloc(struct dpool *dpool,
259                      uint32_t size,
260                      uint8_t defrag)
261 {
262         uint32_t i;
263         uint32_t j;
264         uint32_t count = 0;
265         uint32_t first_entry_index;
266         int rc;
267
268         if (size > dpool->max_alloc_size || size == 0)
269                 return DP_INVALID_INDEX;
270
271         /*
272          * Defrag requires EM move support.
273          */
274         if (defrag != DP_DEFRAG_NONE &&
275             dpool->move_callback == NULL)
276                 return DP_INVALID_INDEX;
277
278         while (1) {
279                 /*
280                  * find <size> consecutive free entries
281                  */
282                 for (i = 0; i < dpool->size; i++) {
283                         if (DP_IS_FREE(dpool->entry[i].flags)) {
284                                 if (count == 0)
285                                         first_entry_index = i;
286
287                                 count++;
288
289                                 if (count == size) {
290                                         for (j = 0; j < size; j++) {
291                                                 dpool->entry[j + first_entry_index].flags = size;
292                                                 if (j == 0)
293                                                         dpool->entry[j + first_entry_index].flags |=
294                                                                 DP_FLAGS_START;
295                                         }
296
297                                         dpool->entry[i].entry_data = 0UL;
298                                         return (first_entry_index + dpool->start_index);
299                                 }
300                         } else {
301                                 count = 0;
302                         }
303                 }
304
305                 /*
306                  * If defragging then do it to it
307                  */
308                 if (defrag != DP_DEFRAG_NONE) {
309                         rc = dpool_defrag(dpool, size, defrag);
310
311                         if (rc < 0)
312                                 return DP_INVALID_INDEX;
313                 } else {
314                         break;
315                 }
316
317                 /*
318                  * If the defrag created enough space then try the
319                  * alloc again else quit.
320                  */
321                 if ((uint32_t)rc < size)
322                         break;
323         }
324
325         return DP_INVALID_INDEX;
326 }
327
328 int dpool_free(struct dpool *dpool,
329                uint32_t index)
330 {
331         uint32_t i;
332         int start = (index - dpool->start_index);
333         uint32_t size;
334
335         if (start < 0)
336                 return -1;
337
338         if (DP_IS_START(dpool->entry[start].flags)) {
339                 size = DP_FLAGS_SIZE(dpool->entry[start].flags);
340                 if (size > dpool->max_alloc_size || size == 0)
341                         return -1;
342
343                 for (i = start; i < (start + size); i++)
344                         dpool->entry[i].flags = 0;
345
346                 return 0;
347         }
348
349         return -1;
350 }
351
352 void dpool_free_all(struct dpool *dpool)
353 {
354         uint32_t i;
355
356         for (i = 0; i < dpool->size; i++)
357                 dpool_free(dpool, dpool->entry[i].index);
358 }
359
360 int dpool_set_entry_data(struct dpool *dpool,
361                          uint32_t index,
362                          uint64_t entry_data)
363 {
364         int start = (index - dpool->start_index);
365
366         if (start < 0)
367                 return -1;
368
369         if (DP_IS_START(dpool->entry[start].flags)) {
370                 dpool->entry[start].entry_data = entry_data;
371                 return 0;
372         }
373
374         return -1;
375 }