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