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