LXR dpdk/drivers/net/bnxt/tf

   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
  16int 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
  55static 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
  88int 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
 251done:
 252        rte_free(free_list);
 253        rte_free(adj_list);
 254        return largest_free_size;
 255}
 256
 257
 258uint32_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
 328int 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
 352void 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
 360int 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