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 129 for (i = 0; i < dpool->size; i++) { 130 if (DP_IS_FREE(dpool->entry[i].flags)) { 131 if (count == 0) 132 index = i; 133 count++; 134 } else if (count > 0) { 135 free_list->entry[free_list->size].index = index; 136 free_list->entry[free_list->size].size = count; 137 138 if (count > largest_free_size) { 139 largest_free_index = free_list->size; 140 largest_free_size = count; 141 } 142 143 free_list->size++; 144 count = 0; 145 } 146 } 147 148 if (free_list->size == 0) 149 largest_free_size = count; 150 151 /* 152 * If using defrag to fit and there's a large enough 153 * space then we are done. 154 */ 155 if (defrag == DP_DEFRAG_TO_FIT && 156 largest_free_size >= entry_size) 157 goto done; 158 159 /* 160 * Create list of entries adjacent to free entries 161 */ 162 count = 0; 163 adj_list->size = 0; 164 used = 0; 165 166 for (i = 0; i < dpool->size; ) { 167 if (DP_IS_USED(dpool->entry[i].flags)) { 168 used++; 169 170 if (count > 0) { 171 adj_list->entry[adj_list->size].index = i; 172 adj_list->entry[adj_list->size].size = 173 DP_FLAGS_SIZE(dpool->entry[i].flags); 174 adj_list->entry[adj_list->size].left = count; 175 176 if (adj_list->size > 0 && used == 1) 177 adj_list->entry[adj_list->size - 1].right = count; 178 179 adj_list->size++; 180 } 181 182 count = 0; 183 i += DP_FLAGS_SIZE(dpool->entry[i].flags); 184 } else { 185 used = 0; 186 count++; 187 i++; 188 } 189 } 190 191 /* 192 * Using the size of the largest free space available 193 * select the adjacency list entry of that size with 194 * the largest left + right + size count. If there 195 * are no entries of that size then decrement the size 196 * and try again. 197 */ 198 max = 0; 199 max_index = 0; 200 max_size = 0; 201 202 for (size = largest_free_size; size > 0; size--) { 203 for (i = 0; i < adj_list->size; i++) { 204 if (adj_list->entry[i].size == size && 205 ((size + 206 adj_list->entry[i].left + 207 adj_list->entry[i].right) > max)) { 208 max = size + 209 adj_list->entry[i].left + 210 adj_list->entry[i].right; 211 max_size = size; 212 max_index = adj_list->entry[i].index; 213 } 214 } 215 216 if (max) 217 break; 218 } 219 220 /* 221 * If the max entry is smaller than the largest_free_size 222 * find the first entry in the free list that it cn fit in to. 223 */ 224 if (max_size < largest_free_size) { 225 for (i = 0; i < free_list->size; i++) { 226 if (free_list->entry[i].size >= max_size) { 227 largest_free_index = i; 228 break; 229 } 230 } 231 } 232 233 /* 234 * If we have a contender then move it to the new spot. 235 */ 236 if (max) { 237 rc = dpool_move(dpool, 238 free_list->entry[largest_free_index].index, 239 max_index); 240 if (rc) { 241 rte_free(free_list); 242 rte_free(adj_list); 243 return rc; 244 } 245 } else { 246 break; 247 } 248 } 249 250 done: 251 rte_free(free_list); 252 rte_free(adj_list); 253 return largest_free_size; 254 } 255 256 257 uint32_t dpool_alloc(struct dpool *dpool, 258 uint32_t size, 259 uint8_t defrag) 260 { 261 uint32_t i; 262 uint32_t j; 263 uint32_t count = 0; 264 uint32_t first_entry_index; 265 int rc; 266 267 if (size > dpool->max_alloc_size || size == 0) 268 return DP_INVALID_INDEX; 269 270 /* 271 * Defrag requires EM move support. 272 */ 273 if (defrag != DP_DEFRAG_NONE && 274 dpool->move_callback == NULL) 275 return DP_INVALID_INDEX; 276 277 while (1) { 278 /* 279 * find <size> consecutive free entries 280 */ 281 for (i = 0; i < dpool->size; i++) { 282 if (DP_IS_FREE(dpool->entry[i].flags)) { 283 if (count == 0) 284 first_entry_index = i; 285 286 count++; 287 288 if (count == size) { 289 for (j = 0; j < size; j++) { 290 dpool->entry[j + first_entry_index].flags = size; 291 if (j == 0) 292 dpool->entry[j + first_entry_index].flags |= 293 DP_FLAGS_START; 294 } 295 296 dpool->entry[i].entry_data = 0UL; 297 return (first_entry_index + dpool->start_index); 298 } 299 } else { 300 count = 0; 301 } 302 } 303 304 /* 305 * If defragging then do it to it 306 */ 307 if (defrag != DP_DEFRAG_NONE) { 308 rc = dpool_defrag(dpool, size, defrag); 309 310 if (rc < 0) 311 return DP_INVALID_INDEX; 312 } else { 313 break; 314 } 315 316 /* 317 * If the defrag created enough space then try the 318 * alloc again else quit. 319 */ 320 if ((uint32_t)rc < size) 321 break; 322 } 323 324 return DP_INVALID_INDEX; 325 } 326 327 int dpool_free(struct dpool *dpool, 328 uint32_t index) 329 { 330 uint32_t i; 331 int start = (index - dpool->start_index); 332 uint32_t size; 333 334 if (start < 0) 335 return -1; 336 337 if (DP_IS_START(dpool->entry[start].flags)) { 338 size = DP_FLAGS_SIZE(dpool->entry[start].flags); 339 if (size > dpool->max_alloc_size || size == 0) 340 return -1; 341 342 for (i = start; i < (start + size); i++) 343 dpool->entry[i].flags = 0; 344 345 return 0; 346 } 347 348 return -1; 349 } 350 351 void dpool_free_all(struct dpool *dpool) 352 { 353 uint32_t i; 354 355 for (i = 0; i < dpool->size; i++) 356 dpool_free(dpool, dpool->entry[i].index); 357 } 358 359 int dpool_set_entry_data(struct dpool *dpool, 360 uint32_t index, 361 uint64_t entry_data) 362 { 363 int start = (index - dpool->start_index); 364 365 if (start < 0) 366 return -1; 367 368 if (DP_IS_START(dpool->entry[start].flags)) { 369 dpool->entry[start].entry_data = entry_data; 370 return 0; 371 } 372 373 return -1; 374 } 375