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