xref: /dpdk/drivers/net/bnxt/tf_core/dpool.c (revision 7917b0d38e92e8b9ec5a870415b791420e10f11a) 
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 
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 
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 
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 
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 
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 
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 
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