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
  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 }