Branch data Line data Source code
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 : 0 : 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 : 0 : parms.nitems = size; 25 : 0 : parms.size = sizeof(struct dpool_entry); 26 : 0 : parms.alignment = 0; 27 : : 28 : 0 : rc = tfp_calloc(&parms); 29 : : 30 [ # # ]: 0 : if (rc) 31 : : return rc; 32 : : 33 : 0 : dpool->entry = parms.mem_va; 34 : 0 : dpool->start_index = start_index; 35 : 0 : dpool->size = size; 36 : 0 : dpool->max_alloc_size = max_alloc_size; 37 : 0 : dpool->user_data = user_data; 38 : 0 : dpool->move_callback = move_callback; 39 : : /* 40 : : * Init entries 41 : : */ 42 [ # # ]: 0 : for (i = 0; i < size; i++) { 43 : 0 : dpool->entry[i].flags = 0; 44 : 0 : dpool->entry[i].index = start_index; 45 : 0 : dpool->entry[i].entry_data = 0UL; 46 : 0 : start_index++; 47 : : } 48 : : 49 : : return 0; 50 : : } 51 : : 52 : 0 : 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 [ # # ]: 0 : if (DP_IS_FREE(dpool->entry[dst_index].flags)) { 60 : 0 : size = DP_FLAGS_SIZE(dpool->entry[src_index].flags); 61 : : 62 : 0 : dpool->entry[dst_index].flags = dpool->entry[src_index].flags; 63 : 0 : dpool->entry[dst_index].entry_data = dpool->entry[src_index].entry_data; 64 : : 65 [ # # ]: 0 : if (dpool->move_callback != NULL) { 66 : 0 : dpool->move_callback(dpool->user_data, 67 : : dpool->entry[src_index].entry_data, 68 : 0 : dst_index + dpool->start_index); 69 : : } 70 : : 71 : 0 : dpool->entry[src_index].flags = 0; 72 : 0 : dpool->entry[src_index].entry_data = 0UL; 73 : : 74 [ # # ]: 0 : for (i = 1; i < size; i++) { 75 : 0 : dpool->entry[dst_index + i].flags = size; 76 : 0 : dpool->entry[src_index + i].flags = 0; 77 : : } 78 : : } else { 79 : : return -1; 80 : : } 81 : : 82 : : return 0; 83 : : } 84 : : 85 : 0 : 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 : 0 : parms.nitems = 1; 105 : 0 : parms.size = sizeof(struct dpool_free_list); 106 : 0 : parms.alignment = 0; 107 : : 108 : 0 : rc = tfp_calloc(&parms); 109 : : 110 [ # # ]: 0 : if (rc) 111 : : return rc; 112 : : 113 : 0 : free_list = (struct dpool_free_list *)parms.mem_va; 114 [ # # ]: 0 : if (free_list == NULL) { 115 : 0 : TFP_DRV_LOG(ERR, "dpool free list allocation failed\n"); 116 : 0 : return -ENOMEM; 117 : : } 118 : : 119 : 0 : parms.nitems = 1; 120 : 0 : parms.size = sizeof(struct dpool_adj_list); 121 : 0 : parms.alignment = 0; 122 : : 123 : 0 : rc = tfp_calloc(&parms); 124 : : 125 [ # # ]: 0 : if (rc) 126 : : return rc; 127 : : 128 : 0 : adj_list = (struct dpool_adj_list *)parms.mem_va; 129 [ # # ]: 0 : if (adj_list == NULL) { 130 : 0 : TFP_DRV_LOG(ERR, "dpool adjacent list allocation failed\n"); 131 : 0 : return -ENOMEM; 132 : : } 133 : : 134 : : while (1) { 135 : : /* 136 : : * Create list of free entries 137 : : */ 138 : 0 : free_list->size = 0; 139 : : largest_free_size = 0; 140 : : largest_free_index = 0; 141 : : count = 0; 142 : : index = 0; 143 : : 144 [ # # ]: 0 : for (i = 0; i < dpool->size; i++) { 145 [ # # ]: 0 : if (DP_IS_FREE(dpool->entry[i].flags)) { 146 [ # # ]: 0 : if (count == 0) 147 : : index = i; 148 : 0 : count++; 149 [ # # ]: 0 : } else if (count > 0) { 150 : 0 : free_list->entry[free_list->size].index = index; 151 : 0 : free_list->entry[free_list->size].size = count; 152 : : 153 [ # # ]: 0 : if (count > largest_free_size) { 154 : : largest_free_index = free_list->size; 155 : : largest_free_size = count; 156 : : } 157 : : 158 : 0 : free_list->size++; 159 : : count = 0; 160 : : } 161 : : } 162 : : 163 [ # # ]: 0 : 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 : 0 : if (defrag == DP_DEFRAG_TO_FIT && 171 [ # # ]: 0 : largest_free_size >= entry_size) 172 : 0 : goto done; 173 : : 174 : : /* 175 : : * Create list of entries adjacent to free entries 176 : : */ 177 : : count = 0; 178 : 0 : adj_list->size = 0; 179 : : used = 0; 180 : : 181 [ # # ]: 0 : for (i = 0; i < dpool->size; ) { 182 [ # # ]: 0 : if (DP_IS_USED(dpool->entry[i].flags)) { 183 : 0 : used++; 184 : : 185 [ # # ]: 0 : if (count > 0) { 186 : 0 : adj_list->entry[adj_list->size].index = i; 187 : 0 : adj_list->entry[adj_list->size].size = 188 : : DP_FLAGS_SIZE(dpool->entry[i].flags); 189 : 0 : adj_list->entry[adj_list->size].left = count; 190 : : 191 [ # # # # ]: 0 : if (adj_list->size > 0 && used == 1) 192 : 0 : adj_list->entry[adj_list->size - 1].right = count; 193 : : 194 : 0 : adj_list->size++; 195 : : } 196 : : 197 : : count = 0; 198 : 0 : i += DP_FLAGS_SIZE(dpool->entry[i].flags); 199 : : } else { 200 : : used = 0; 201 : 0 : count++; 202 : 0 : 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 [ # # ]: 0 : for (size = largest_free_size; size > 0; size--) { 218 [ # # ]: 0 : for (i = 0; i < adj_list->size; i++) { 219 [ # # ]: 0 : if (adj_list->entry[i].size == size && 220 : 0 : ((size + 221 : 0 : adj_list->entry[i].left + 222 [ # # ]: 0 : 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 : 0 : max_index = adj_list->entry[i].index; 228 : : } 229 : : } 230 : : 231 [ # # ]: 0 : 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 [ # # ]: 0 : if (max_size < largest_free_size) { 240 [ # # ]: 0 : for (i = 0; i < free_list->size; i++) { 241 [ # # ]: 0 : 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 [ # # ]: 0 : if (max) { 252 : 0 : rc = dpool_move(dpool, 253 : : free_list->entry[largest_free_index].index, 254 : : max_index); 255 [ # # ]: 0 : if (rc) { 256 : 0 : tfp_free(free_list); 257 : 0 : tfp_free(adj_list); 258 : 0 : return rc; 259 : : } 260 : : } else { 261 : : break; 262 : : } 263 : : } 264 : : 265 : 0 : done: 266 : 0 : tfp_free(free_list); 267 : 0 : tfp_free(adj_list); 268 : 0 : return largest_free_size; 269 : : } 270 : : 271 : 0 : 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 [ # # # # ]: 0 : if (size > dpool->max_alloc_size || size == 0) 282 : : return DP_INVALID_INDEX; 283 : : 284 : : /* 285 : : * Defrag requires EM move support. 286 : : */ 287 [ # # ]: 0 : if (defrag != DP_DEFRAG_NONE && 288 [ # # ]: 0 : dpool->move_callback == NULL) 289 : : return DP_INVALID_INDEX; 290 : : 291 : : while (1) { 292 : : /* 293 : : * find <size> consecutive free entries 294 : : */ 295 [ # # ]: 0 : for (i = 0; i < dpool->size; i++) { 296 [ # # ]: 0 : if (DP_IS_FREE(dpool->entry[i].flags)) { 297 [ # # ]: 0 : if (count == 0) 298 : : first_entry_index = i; 299 : : 300 : 0 : count++; 301 : : 302 [ # # ]: 0 : if (count == size) { 303 [ # # ]: 0 : for (j = 0; j < size; j++) { 304 : 0 : dpool->entry[j + first_entry_index].flags = size; 305 [ # # ]: 0 : if (j == 0) 306 : 0 : dpool->entry[j + first_entry_index].flags |= 307 : : DP_FLAGS_START; 308 : : } 309 : : 310 : 0 : dpool->entry[i].entry_data = 0UL; 311 : 0 : 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 [ # # ]: 0 : if (defrag != DP_DEFRAG_NONE) { 322 : 0 : rc = dpool_defrag(dpool, size, defrag); 323 : : 324 [ # # ]: 0 : 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 [ # # ]: 0 : if ((uint32_t)rc < size) 335 : : break; 336 : : } 337 : : 338 : : return DP_INVALID_INDEX; 339 : : } 340 : : 341 : 0 : int dpool_free(struct dpool *dpool, 342 : : uint32_t index) 343 : : { 344 : : uint32_t i; 345 : 0 : int start = (index - dpool->start_index); 346 : : uint32_t size; 347 : : 348 [ # # ]: 0 : if (start < 0) 349 : : return -1; 350 : : 351 [ # # ]: 0 : if (DP_IS_START(dpool->entry[start].flags)) { 352 : 0 : size = DP_FLAGS_SIZE(dpool->entry[start].flags); 353 [ # # # # ]: 0 : if (size > dpool->max_alloc_size || size == 0) 354 : : return -1; 355 : : 356 [ # # ]: 0 : for (i = start; i < (start + size); i++) 357 : 0 : dpool->entry[i].flags = 0; 358 : : 359 : : return 0; 360 : : } 361 : : 362 : : return -1; 363 : : } 364 : : 365 : 0 : void dpool_free_all(struct dpool *dpool) 366 : : { 367 : : uint32_t i; 368 : : 369 [ # # ]: 0 : for (i = 0; i < dpool->size; i++) 370 : 0 : dpool_free(dpool, dpool->entry[i].index); 371 : 0 : } 372 : : 373 : 0 : int dpool_set_entry_data(struct dpool *dpool, 374 : : uint32_t index, 375 : : uint64_t entry_data) 376 : : { 377 : 0 : int start = (index - dpool->start_index); 378 : : 379 [ # # ]: 0 : if (start < 0) 380 : : return -1; 381 : : 382 [ # # ]: 0 : if (DP_IS_START(dpool->entry[start].flags)) { 383 : 0 : dpool->entry[start].entry_data = entry_data; 384 : 0 : return 0; 385 : : } 386 : : 387 : : return -1; 388 : : }