drivers/net/bnxt/tf_core/dpool.c

   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 }