xref: /dpdk/drivers/net/bnxt/tf_core/dpool.c (revision 10eaf41d) 
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 }
376