LCOV - code coverage report
Current view: top level - drivers/net/bnxt/tf_core - bitalloc.c (source / functions) Hit Total Coverage
Test: Code coverage Lines: 0 184 0.0 %
Date: 2024-01-22 16:13:49 Functions: 0 19 0.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 126 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                 :            : 
       6                 :            : #include "bitalloc.h"
       7                 :            : 
       8                 :            : #define BITALLOC_MAX_LEVELS 6
       9                 :            : 
      10                 :            : /* Finds the last bit set plus 1, equivalent to gcc __builtin_fls */
      11                 :            : static int
      12                 :          0 : ba_fls(bitalloc_word_t v)
      13                 :            : {
      14                 :            :         int c = 32;
      15                 :            : 
      16         [ #  # ]:          0 :         if (!v)
      17                 :            :                 return 0;
      18                 :            : 
      19         [ #  # ]:          0 :         if (!(v & 0xFFFF0000u)) {
      20                 :          0 :                 v <<= 16;
      21                 :            :                 c -= 16;
      22                 :            :         }
      23         [ #  # ]:          0 :         if (!(v & 0xFF000000u)) {
      24                 :          0 :                 v <<= 8;
      25                 :          0 :                 c -= 8;
      26                 :            :         }
      27         [ #  # ]:          0 :         if (!(v & 0xF0000000u)) {
      28                 :          0 :                 v <<= 4;
      29                 :          0 :                 c -= 4;
      30                 :            :         }
      31         [ #  # ]:          0 :         if (!(v & 0xC0000000u)) {
      32                 :          0 :                 v <<= 2;
      33                 :          0 :                 c -= 2;
      34                 :            :         }
      35         [ #  # ]:          0 :         if (!(v & 0x80000000u)) {
      36                 :            :                 v <<= 1;
      37                 :          0 :                 c -= 1;
      38                 :            :         }
      39                 :            : 
      40                 :            :         return c;
      41                 :            : }
      42                 :            : 
      43                 :            : /* Finds the first bit set plus 1, equivalent to gcc __builtin_ffs */
      44                 :            : static int
      45                 :          0 : ba_ffs(bitalloc_word_t v)
      46                 :            : {
      47                 :            :         int c; /* c will be the number of zero bits on the right plus 1 */
      48                 :            : 
      49                 :          0 :         v &= -v;
      50         [ #  # ]:          0 :         c = v ? 32 : 0;
      51                 :            : 
      52         [ #  # ]:          0 :         if (v & 0x0000FFFF)
      53                 :          0 :                 c -= 16;
      54         [ #  # ]:          0 :         if (v & 0x00FF00FF)
      55                 :          0 :                 c -= 8;
      56         [ #  # ]:          0 :         if (v & 0x0F0F0F0F)
      57                 :          0 :                 c -= 4;
      58         [ #  # ]:          0 :         if (v & 0x33333333)
      59                 :          0 :                 c -= 2;
      60         [ #  # ]:          0 :         if (v & 0x55555555)
      61                 :          0 :                 c -= 1;
      62                 :            : 
      63                 :          0 :         return c;
      64                 :            : }
      65                 :            : 
      66                 :            : int
      67                 :          0 : ba_init(struct bitalloc *pool, int size, bool free)
      68                 :            : {
      69                 :            :         bitalloc_word_t *mem = (bitalloc_word_t *)pool;
      70                 :            :         int       i;
      71                 :            : 
      72                 :            :         /* Initialize */
      73                 :          0 :         pool->size = 0;
      74                 :            : 
      75         [ #  # ]:          0 :         if (size < 1 || size > BITALLOC_MAX_SIZE)
      76                 :            :                 return -1;
      77                 :            : 
      78                 :            :         /* Zero structure */
      79                 :            :         for (i = 0;
      80   [ #  #  #  #  :          0 :              i < (int)(BITALLOC_SIZEOF(size) / sizeof(bitalloc_word_t));
          #  #  #  #  #  
                      # ]
      81                 :          0 :              i++)
      82                 :          0 :                 mem[i] = 0;
      83                 :            : 
      84                 :            :         /* Initialize */
      85                 :          0 :         pool->size = size;
      86                 :            : 
      87                 :            :         /* Embed number of words of next level, after each level */
      88                 :            :         int words[BITALLOC_MAX_LEVELS];
      89                 :            :         int lev = 0;
      90                 :            :         int offset = 0;
      91                 :            : 
      92                 :          0 :         words[0] = (size + 31) / 32;
      93         [ #  # ]:          0 :         while (words[lev] > 1) {
      94                 :          0 :                 lev++;
      95                 :          0 :                 words[lev] = (words[lev - 1] + 31) / 32;
      96                 :            :         }
      97                 :            : 
      98         [ #  # ]:          0 :         while (lev) {
      99                 :          0 :                 offset += words[lev];
     100                 :          0 :                 pool->storage[offset++] = words[--lev];
     101                 :            :         }
     102                 :            : 
     103                 :            :         /* Free the entire pool if it is required*/
     104         [ #  # ]:          0 :         if (free) {
     105         [ #  # ]:          0 :                 for (i = 0; i < size; i++)
     106                 :          0 :                         ba_free(pool, i);
     107                 :            :         }
     108                 :            : 
     109                 :            :         return 0;
     110                 :            : }
     111                 :            : 
     112                 :            : static int
     113                 :          0 : ba_alloc_helper(struct bitalloc *pool,
     114                 :            :                 int              offset,
     115                 :            :                 int              words,
     116                 :            :                 unsigned int     size,
     117                 :            :                 int              index,
     118                 :            :                 int             *clear)
     119                 :            : {
     120                 :          0 :         bitalloc_word_t *storage = &pool->storage[offset];
     121                 :          0 :         int       loc = ba_ffs(storage[index]);
     122                 :            :         int       r;
     123                 :            : 
     124         [ #  # ]:          0 :         if (loc == 0)
     125                 :            :                 return -1;
     126                 :            : 
     127                 :          0 :         loc--;
     128                 :            : 
     129         [ #  # ]:          0 :         if (pool->size > size) {
     130                 :          0 :                 r = ba_alloc_helper(pool,
     131                 :          0 :                                     offset + words + 1,
     132                 :          0 :                                     storage[words],
     133                 :            :                                     size * 32,
     134                 :          0 :                                     index * 32 + loc,
     135                 :            :                                     clear);
     136                 :            :         } else {
     137                 :          0 :                 r = index * 32 + loc;
     138                 :          0 :                 *clear = 1;
     139                 :          0 :                 pool->free_count--;
     140                 :            :         }
     141                 :            : 
     142         [ #  # ]:          0 :         if (*clear) {
     143                 :          0 :                 storage[index] &= ~(1 << loc);
     144                 :          0 :                 *clear = (storage[index] == 0);
     145                 :            :         }
     146                 :            : 
     147                 :            :         return r;
     148                 :            : }
     149                 :            : 
     150                 :            : int
     151                 :          0 : ba_alloc(struct bitalloc *pool)
     152                 :            : {
     153                 :          0 :         int clear = 0;
     154                 :            : 
     155                 :          0 :         return ba_alloc_helper(pool, 0, 1, 32, 0, &clear);
     156                 :            : }
     157                 :            : 
     158                 :            : /**
     159                 :            :  * Help function to alloc entry from highest available index
     160                 :            :  *
     161                 :            :  * Searching the pool from highest index for the empty entry.
     162                 :            :  *
     163                 :            :  * [in] pool
     164                 :            :  *   Pointer to the resource pool
     165                 :            :  *
     166                 :            :  * [in] offset
     167                 :            :  *   Offset of the storage in the pool
     168                 :            :  *
     169                 :            :  * [in] words
     170                 :            :  *   Number of words in this level
     171                 :            :  *
     172                 :            :  * [in] size
     173                 :            :  *   Number of entries in this level
     174                 :            :  *
     175                 :            :  * [in] index
     176                 :            :  *   Index of words that has the entry
     177                 :            :  *
     178                 :            :  * [in] clear
     179                 :            :  *   Indicate if a bit needs to be clear due to the entry is allocated
     180                 :            :  *
     181                 :            :  * Returns:
     182                 :            :  *     0 - Success
     183                 :            :  *    -1 - Failure
     184                 :            :  */
     185                 :            : static int
     186                 :          0 : ba_alloc_reverse_helper(struct bitalloc *pool,
     187                 :            :                         int offset,
     188                 :            :                         int words,
     189                 :            :                         unsigned int size,
     190                 :            :                         int index,
     191                 :            :                         int *clear)
     192                 :            : {
     193                 :          0 :         bitalloc_word_t *storage = &pool->storage[offset];
     194                 :          0 :         int loc = ba_fls(storage[index]);
     195                 :            :         int r;
     196                 :            : 
     197         [ #  # ]:          0 :         if (loc == 0)
     198                 :            :                 return -1;
     199                 :            : 
     200                 :          0 :         loc--;
     201                 :            : 
     202         [ #  # ]:          0 :         if (pool->size > size) {
     203                 :          0 :                 r = ba_alloc_reverse_helper(pool,
     204                 :          0 :                                             offset + words + 1,
     205                 :          0 :                                             storage[words],
     206                 :            :                                             size * 32,
     207                 :          0 :                                             index * 32 + loc,
     208                 :            :                                             clear);
     209                 :            :         } else {
     210                 :          0 :                 r = index * 32 + loc;
     211                 :          0 :                 *clear = 1;
     212                 :          0 :                 pool->free_count--;
     213                 :            :         }
     214                 :            : 
     215         [ #  # ]:          0 :         if (*clear) {
     216                 :          0 :                 storage[index] &= ~(1 << loc);
     217                 :          0 :                 *clear = (storage[index] == 0);
     218                 :            :         }
     219                 :            : 
     220                 :            :         return r;
     221                 :            : }
     222                 :            : 
     223                 :            : int
     224                 :          0 : ba_alloc_reverse(struct bitalloc *pool)
     225                 :            : {
     226                 :          0 :         int clear = 0;
     227                 :            : 
     228                 :          0 :         return ba_alloc_reverse_helper(pool, 0, 1, 32, 0, &clear);
     229                 :            : }
     230                 :            : 
     231                 :            : static int
     232                 :          0 : ba_alloc_index_helper(struct bitalloc *pool,
     233                 :            :                       int              offset,
     234                 :            :                       int              words,
     235                 :            :                       unsigned int     size,
     236                 :            :                       int             *index,
     237                 :            :                       int             *clear)
     238                 :            : {
     239                 :          0 :         bitalloc_word_t *storage = &pool->storage[offset];
     240                 :            :         int       loc;
     241                 :            :         int       r;
     242                 :            : 
     243         [ #  # ]:          0 :         if (pool->size > size)
     244                 :          0 :                 r = ba_alloc_index_helper(pool,
     245                 :          0 :                                           offset + words + 1,
     246                 :          0 :                                           storage[words],
     247                 :            :                                           size * 32,
     248                 :            :                                           index,
     249                 :            :                                           clear);
     250                 :            :         else
     251                 :            :                 r = 1; /* Check if already allocated */
     252                 :            : 
     253                 :          0 :         loc = (*index % 32);
     254                 :          0 :         *index = *index / 32;
     255                 :            : 
     256         [ #  # ]:          0 :         if (r == 1) {
     257         [ #  # ]:          0 :                 r = (storage[*index] & (1 << loc)) ? 0 : -1;
     258                 :            :                 if (r == 0) {
     259                 :          0 :                         *clear = 1;
     260                 :          0 :                         pool->free_count--;
     261                 :            :                 }
     262                 :            :         }
     263                 :            : 
     264         [ #  # ]:          0 :         if (*clear) {
     265                 :          0 :                 storage[*index] &= ~(1 << loc);
     266                 :          0 :                 *clear = (storage[*index] == 0);
     267                 :            :         }
     268                 :            : 
     269                 :          0 :         return r;
     270                 :            : }
     271                 :            : 
     272                 :            : int
     273                 :          0 : ba_alloc_index(struct bitalloc *pool, int index)
     274                 :            : {
     275                 :          0 :         int clear = 0;
     276                 :          0 :         int index_copy = index;
     277                 :            : 
     278   [ #  #  #  # ]:          0 :         if (index < 0 || index >= (int)pool->size)
     279                 :            :                 return -1;
     280                 :            : 
     281         [ #  # ]:          0 :         if (ba_alloc_index_helper(pool, 0, 1, 32, &index_copy, &clear) >= 0)
     282                 :            :                 return index;
     283                 :            :         else
     284                 :          0 :                 return -1;
     285                 :            : }
     286                 :            : 
     287                 :            : static int
     288                 :          0 : ba_inuse_helper(struct bitalloc *pool,
     289                 :            :                 int              offset,
     290                 :            :                 int              words,
     291                 :            :                 unsigned int     size,
     292                 :            :                 int             *index)
     293                 :            : {
     294                 :          0 :         bitalloc_word_t *storage = &pool->storage[offset];
     295                 :            :         int       loc;
     296                 :            :         int       r;
     297                 :            : 
     298         [ #  # ]:          0 :         if (pool->size > size)
     299                 :          0 :                 r = ba_inuse_helper(pool,
     300                 :          0 :                                     offset + words + 1,
     301                 :          0 :                                     storage[words],
     302                 :            :                                     size * 32,
     303                 :            :                                     index);
     304                 :            :         else
     305                 :            :                 r = 1; /* Check if in use */
     306                 :            : 
     307                 :          0 :         loc = (*index % 32);
     308                 :          0 :         *index = *index / 32;
     309                 :            : 
     310         [ #  # ]:          0 :         if (r == 1)
     311         [ #  # ]:          0 :                 r = (storage[*index] & (1 << loc)) ? -1 : 0;
     312                 :            : 
     313                 :          0 :         return r;
     314                 :            : }
     315                 :            : 
     316                 :            : int
     317                 :          0 : ba_inuse(struct bitalloc *pool, int index)
     318                 :            : {
     319   [ #  #  #  # ]:          0 :         if (index < 0 || index >= (int)pool->size)
     320                 :            :                 return -1;
     321                 :            : 
     322                 :          0 :         return ba_inuse_helper(pool, 0, 1, 32, &index) == 0;
     323                 :            : }
     324                 :            : 
     325                 :            : static int
     326                 :          0 : ba_free_helper(struct bitalloc *pool,
     327                 :            :                int              offset,
     328                 :            :                int              words,
     329                 :            :                unsigned int     size,
     330                 :            :                int             *index)
     331                 :            : {
     332                 :          0 :         bitalloc_word_t *storage = &pool->storage[offset];
     333                 :            :         int       loc;
     334                 :            :         int       r;
     335                 :            : 
     336         [ #  # ]:          0 :         if (pool->size > size)
     337                 :          0 :                 r = ba_free_helper(pool,
     338                 :          0 :                                    offset + words + 1,
     339                 :          0 :                                    storage[words],
     340                 :            :                                    size * 32,
     341                 :            :                                    index);
     342                 :            :         else
     343                 :            :                 r = 1; /* Check if already free */
     344                 :            : 
     345                 :          0 :         loc = (*index % 32);
     346                 :          0 :         *index = *index / 32;
     347                 :            : 
     348         [ #  # ]:          0 :         if (r == 1) {
     349         [ #  # ]:          0 :                 r = (storage[*index] & (1 << loc)) ? -1 : 0;
     350                 :            :                 if (r == 0)
     351                 :          0 :                         pool->free_count++;
     352                 :            :         }
     353                 :            : 
     354         [ #  # ]:          0 :         if (r == 0)
     355                 :          0 :                 storage[*index] |= (1 << loc);
     356                 :            : 
     357                 :          0 :         return r;
     358                 :            : }
     359                 :            : 
     360                 :            : int
     361                 :          0 : ba_free(struct bitalloc *pool, int index)
     362                 :            : {
     363   [ #  #  #  # ]:          0 :         if (index < 0 || index >= (int)pool->size)
     364                 :            :                 return -1;
     365                 :            : 
     366                 :          0 :         return ba_free_helper(pool, 0, 1, 32, &index);
     367                 :            : }
     368                 :            : 
     369                 :            : int
     370                 :          0 : ba_inuse_free(struct bitalloc *pool, int index)
     371                 :            : {
     372   [ #  #  #  # ]:          0 :         if (index < 0 || index >= (int)pool->size)
     373                 :            :                 return -1;
     374                 :            : 
     375                 :          0 :         return ba_free_helper(pool, 0, 1, 32, &index) + 1;
     376                 :            : }
     377                 :            : 
     378                 :            : int
     379                 :          0 : ba_free_count(struct bitalloc *pool)
     380                 :            : {
     381                 :          0 :         return (int)pool->free_count;
     382                 :            : }
     383                 :            : 
     384                 :          0 : int ba_inuse_count(struct bitalloc *pool)
     385                 :            : {
     386                 :          0 :         return (int)(pool->size) - (int)(pool->free_count);
     387                 :            : }
     388                 :            : 
     389                 :            : static int
     390                 :          0 : ba_find_next_helper(struct bitalloc *pool,
     391                 :            :                     int              offset,
     392                 :            :                     int              words,
     393                 :            :                     unsigned int     size,
     394                 :            :                     int             *index,
     395                 :            :                     int              free)
     396                 :            : {
     397                 :          0 :         bitalloc_word_t *storage = &pool->storage[offset];
     398                 :            :         int       loc, r, bottom = 0;
     399                 :            : 
     400         [ #  # ]:          0 :         if (pool->size > size)
     401                 :          0 :                 r = ba_find_next_helper(pool,
     402                 :          0 :                                         offset + words + 1,
     403                 :          0 :                                         storage[words],
     404                 :            :                                         size * 32,
     405                 :            :                                         index,
     406                 :            :                                         free);
     407                 :            :         else
     408                 :            :                 bottom = 1; /* Bottom of tree */
     409                 :            : 
     410                 :          0 :         loc = (*index % 32);
     411                 :          0 :         *index = *index / 32;
     412                 :            : 
     413         [ #  # ]:          0 :         if (bottom) {
     414                 :          0 :                 int bit_index = *index * 32;
     415                 :            : 
     416                 :          0 :                 loc = ba_ffs(~storage[*index] & ((bitalloc_word_t)-1 << loc));
     417         [ #  # ]:          0 :                 if (loc > 0) {
     418                 :          0 :                         loc--;
     419                 :          0 :                         r = (bit_index + loc);
     420         [ #  # ]:          0 :                         if (r >= (int)pool->size)
     421                 :            :                                 r = -1;
     422                 :            :                 } else {
     423                 :            :                         /* Loop over array at bottom of tree */
     424                 :            :                         r = -1;
     425                 :          0 :                         bit_index += 32;
     426                 :          0 :                         *index = *index + 1;
     427         [ #  # ]:          0 :                         while ((int)pool->size > bit_index) {
     428                 :          0 :                                 loc = ba_ffs(~storage[*index]);
     429                 :            : 
     430         [ #  # ]:          0 :                                 if (loc > 0) {
     431                 :          0 :                                         loc--;
     432                 :          0 :                                         r = (bit_index + loc);
     433         [ #  # ]:          0 :                                         if (r >= (int)pool->size)
     434                 :            :                                                 r = -1;
     435                 :            :                                         break;
     436                 :            :                                 }
     437                 :          0 :                                 bit_index += 32;
     438                 :          0 :                                 *index = *index + 1;
     439                 :            :                         }
     440                 :            :                 }
     441                 :            :         }
     442                 :            : 
     443         [ #  # ]:          0 :         if (r >= 0 && (free)) {
     444         [ #  # ]:          0 :                 if (bottom)
     445                 :          0 :                         pool->free_count++;
     446                 :          0 :                 storage[*index] |= (1 << loc);
     447                 :            :         }
     448                 :            : 
     449                 :          0 :         return r;
     450                 :            : }
     451                 :            : 
     452                 :            : int
     453                 :          0 : ba_find_next_inuse(struct bitalloc *pool, int index)
     454                 :            : {
     455         [ #  # ]:          0 :         if (index < 0 ||
     456         [ #  # ]:          0 :             index >= (int)pool->size ||
     457         [ #  # ]:          0 :             pool->free_count == pool->size)
     458                 :            :                 return -1;
     459                 :            : 
     460                 :          0 :         return ba_find_next_helper(pool, 0, 1, 32, &index, 0);
     461                 :            : }
     462                 :            : 
     463                 :            : int
     464                 :          0 : ba_find_next_inuse_free(struct bitalloc *pool, int index)
     465                 :            : {
     466         [ #  # ]:          0 :         if (index < 0 ||
     467         [ #  # ]:          0 :             index >= (int)pool->size ||
     468         [ #  # ]:          0 :             pool->free_count == pool->size)
     469                 :            :                 return -1;
     470                 :            : 
     471                 :          0 :         return ba_find_next_helper(pool, 0, 1, 32, &index, 1);
     472                 :            : }

Generated by: LCOV version 1.14