LCOV - code coverage report
Current view: top level - drivers/net/bnxt/tf_core - dpool.c (source / functions) Hit Total Coverage
Test: Code coverage Lines: 0 135 0.0 %
Date: 2024-01-22 15:55:54 Functions: 0 7 0.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 104 0.0 %

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

Generated by: LCOV version 1.14