Line data    Source code

       1             : /*   SPDX-License-Identifier: BSD-3-Clause
       2             :  *   Copyright (C) 2016 Intel Corporation.
       3             :  *   All rights reserved.
       4             :  */
       5             : 
       6             : #include "spdk/stdinc.h"
       7             : 
       8             : #include "spdk/bit_array.h"
       9             : #include "spdk/bit_pool.h"
      10             : #include "spdk/env.h"
      11             : 
      12             : #include "spdk/likely.h"
      13             : #include "spdk/util.h"
      14             : 
      15             : typedef uint64_t spdk_bit_array_word;
      16             : #define SPDK_BIT_ARRAY_WORD_TZCNT(x)    (__builtin_ctzll(x))
      17             : #define SPDK_BIT_ARRAY_WORD_POPCNT(x)   (__builtin_popcountll(x))
      18             : #define SPDK_BIT_ARRAY_WORD_C(x)        ((spdk_bit_array_word)(x))
      19             : #define SPDK_BIT_ARRAY_WORD_BYTES       sizeof(spdk_bit_array_word)
      20             : #define SPDK_BIT_ARRAY_WORD_BITS        (SPDK_BIT_ARRAY_WORD_BYTES * 8)
      21             : #define SPDK_BIT_ARRAY_WORD_INDEX_SHIFT spdk_u32log2(SPDK_BIT_ARRAY_WORD_BITS)
      22             : #define SPDK_BIT_ARRAY_WORD_INDEX_MASK  ((1u << SPDK_BIT_ARRAY_WORD_INDEX_SHIFT) - 1)
      23             : 
      24             : struct spdk_bit_array {
      25             :         uint32_t bit_count;
      26             :         spdk_bit_array_word words[];
      27             : };
      28             : 
      29             : struct spdk_bit_array *
      30        4035 : spdk_bit_array_create(uint32_t num_bits)
      31             : {
      32        4035 :         struct spdk_bit_array *ba = NULL;
      33             : 
      34        4035 :         spdk_bit_array_resize(&ba, num_bits);
      35             : 
      36        8070 :         return ba;
      37        4035 : }
      38             : 
      39             : void
      40        4065 : spdk_bit_array_free(struct spdk_bit_array **bap)
      41             : {
      42        4065 :         struct spdk_bit_array *ba;
      43             : 
      44        4065 :         if (!bap) {
      45           1 :                 return;
      46             :         }
      47             : 
      48        4064 :         ba = *bap;
      49        4064 :         *bap = NULL;
      50        4064 :         spdk_free(ba);
      51        4065 : }
      52             : 
      53             : static inline uint32_t
      54       12779 : bit_array_word_count(uint32_t num_bits)
      55             : {
      56       12779 :         return (num_bits + SPDK_BIT_ARRAY_WORD_BITS - 1) >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT;
      57             : }
      58             : 
      59             : static inline spdk_bit_array_word
      60       18428 : bit_array_word_mask(uint32_t num_bits)
      61             : {
      62       18428 :         assert(num_bits < SPDK_BIT_ARRAY_WORD_BITS);
      63       18428 :         return (SPDK_BIT_ARRAY_WORD_C(1) << num_bits) - 1;
      64             : }
      65             : 
      66             : int
      67        7706 : spdk_bit_array_resize(struct spdk_bit_array **bap, uint32_t num_bits)
      68             : {
      69        7706 :         struct spdk_bit_array *new_ba;
      70        7706 :         uint32_t old_word_count, new_word_count;
      71        7706 :         size_t new_size;
      72             : 
      73             :         /*
      74             :          * Max number of bits allowed is UINT32_MAX - 1, because we use UINT32_MAX to denote
      75             :          * when a set or cleared bit cannot be found.
      76             :          */
      77        7706 :         if (!bap || num_bits == UINT32_MAX) {
      78           1 :                 return -EINVAL;
      79             :         }
      80             : 
      81        7705 :         new_word_count = bit_array_word_count(num_bits);
      82        7705 :         new_size = offsetof(struct spdk_bit_array, words) + new_word_count * SPDK_BIT_ARRAY_WORD_BYTES;
      83             : 
      84             :         /*
      85             :          * Always keep one extra word with a 0 and a 1 past the actual required size so that the
      86             :          * find_first functions can just keep going until they match.
      87             :          */
      88        7705 :         new_size += SPDK_BIT_ARRAY_WORD_BYTES;
      89             : 
      90        7705 :         new_ba = (struct spdk_bit_array *)spdk_realloc(*bap, new_size, 64);
      91        7705 :         if (!new_ba) {
      92           0 :                 return -ENOMEM;
      93             :         }
      94             : 
      95             :         /*
      96             :          * Set up special extra word (see above comment about find_first_clear).
      97             :          *
      98             :          * This is set to 0b10 so that find_first_clear will find a 0 at the very first
      99             :          * bit past the end of the buffer, and find_first_set will find a 1 at the next bit
     100             :          * past that.
     101             :          */
     102        7705 :         new_ba->words[new_word_count] = 0x2;
     103             : 
     104        7705 :         if (*bap == NULL) {
     105        4035 :                 old_word_count = 0;
     106        4035 :                 new_ba->bit_count = 0;
     107        4035 :         } else {
     108        3670 :                 old_word_count = bit_array_word_count(new_ba->bit_count);
     109             :         }
     110             : 
     111        7705 :         if (new_word_count > old_word_count) {
     112             :                 /* Zero out new entries */
     113        4154 :                 memset(&new_ba->words[old_word_count], 0,
     114        4154 :                        (new_word_count - old_word_count) * SPDK_BIT_ARRAY_WORD_BYTES);
     115        7705 :         } else if (new_word_count == old_word_count && num_bits < new_ba->bit_count) {
     116             :                 /* Make sure any existing partial last word is cleared beyond the new num_bits. */
     117           6 :                 uint32_t last_word_bits;
     118           6 :                 spdk_bit_array_word mask;
     119             : 
     120           6 :                 last_word_bits = num_bits & SPDK_BIT_ARRAY_WORD_INDEX_MASK;
     121           6 :                 mask = bit_array_word_mask(last_word_bits);
     122           6 :                 new_ba->words[old_word_count - 1] &= mask;
     123           6 :         }
     124             : 
     125        7705 :         new_ba->bit_count = num_bits;
     126        7705 :         *bap = new_ba;
     127        7705 :         return 0;
     128        7706 : }
     129             : 
     130             : uint32_t
     131       17003 : spdk_bit_array_capacity(const struct spdk_bit_array *ba)
     132             : {
     133       17003 :         return ba->bit_count;
     134             : }
     135             : 
     136             : static inline int
     137      173699 : bit_array_get_word(const struct spdk_bit_array *ba, uint32_t bit_index,
     138             :                    uint32_t *word_index, uint32_t *word_bit_index)
     139             : {
     140      173699 :         if (spdk_unlikely(bit_index >= ba->bit_count)) {
     141         150 :                 return -EINVAL;
     142             :         }
     143             : 
     144      173549 :         *word_index = bit_index >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT;
     145      173549 :         *word_bit_index = bit_index & SPDK_BIT_ARRAY_WORD_INDEX_MASK;
     146             : 
     147      173549 :         return 0;
     148      173699 : }
     149             : 
     150             : bool
     151       58018 : spdk_bit_array_get(const struct spdk_bit_array *ba, uint32_t bit_index)
     152             : {
     153       58018 :         uint32_t word_index, word_bit_index;
     154             : 
     155       58018 :         if (bit_array_get_word(ba, bit_index, &word_index, &word_bit_index)) {
     156         148 :                 return false;
     157             :         }
     158             : 
     159       57870 :         return (ba->words[word_index] >> word_bit_index) & 1U;
     160       58018 : }
     161             : 
     162             : int
     163      103436 : spdk_bit_array_set(struct spdk_bit_array *ba, uint32_t bit_index)
     164             : {
     165      103436 :         uint32_t word_index, word_bit_index;
     166             : 
     167      103436 :         if (bit_array_get_word(ba, bit_index, &word_index, &word_bit_index)) {
     168           1 :                 return -EINVAL;
     169             :         }
     170             : 
     171      103435 :         ba->words[word_index] |= (SPDK_BIT_ARRAY_WORD_C(1) << word_bit_index);
     172      103435 :         return 0;
     173      103436 : }
     174             : 
     175             : void
     176       12245 : spdk_bit_array_clear(struct spdk_bit_array *ba, uint32_t bit_index)
     177             : {
     178       12245 :         uint32_t word_index, word_bit_index;
     179             : 
     180       12245 :         if (bit_array_get_word(ba, bit_index, &word_index, &word_bit_index)) {
     181             :                 /*
     182             :                  * Clearing past the end of the bit array is a no-op, since bit past the end
     183             :                  * are implicitly 0.
     184             :                  */
     185           1 :                 return;
     186             :         }
     187             : 
     188       12244 :         ba->words[word_index] &= ~(SPDK_BIT_ARRAY_WORD_C(1) << word_bit_index);
     189       12245 : }
     190             : 
     191             : static inline uint32_t
     192       18425 : bit_array_find_first(const struct spdk_bit_array *ba, uint32_t start_bit_index,
     193             :                      spdk_bit_array_word xor_mask)
     194             : {
     195       18425 :         uint32_t word_index, first_word_bit_index;
     196       18425 :         spdk_bit_array_word word, first_word_mask;
     197       18425 :         const spdk_bit_array_word *words, *cur_word;
     198             : 
     199       18425 :         if (spdk_unlikely(start_bit_index >= ba->bit_count)) {
     200           3 :                 return ba->bit_count;
     201             :         }
     202             : 
     203       18422 :         word_index = start_bit_index >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT;
     204       18422 :         words = ba->words;
     205       18422 :         cur_word = &words[word_index];
     206             : 
     207             :         /*
     208             :          * Special case for first word: skip start_bit_index % SPDK_BIT_ARRAY_WORD_BITS bits
     209             :          * within the first word.
     210             :          */
     211       18422 :         first_word_bit_index = start_bit_index & SPDK_BIT_ARRAY_WORD_INDEX_MASK;
     212       18422 :         first_word_mask = bit_array_word_mask(first_word_bit_index);
     213             : 
     214       18422 :         word = (*cur_word ^ xor_mask) & ~first_word_mask;
     215             : 
     216             :         /*
     217             :          * spdk_bit_array_resize() guarantees that an extra word with a 1 and a 0 will always be
     218             :          * at the end of the words[] array, so just keep going until a word matches.
     219             :          */
     220       24081 :         while (word == 0) {
     221        5659 :                 word = *++cur_word ^ xor_mask;
     222             :         }
     223             : 
     224       18422 :         return ((uintptr_t)cur_word - (uintptr_t)words) * 8 + SPDK_BIT_ARRAY_WORD_TZCNT(word);
     225       18425 : }
     226             : 
     227             : 
     228             : uint32_t
     229        1726 : spdk_bit_array_find_first_set(const struct spdk_bit_array *ba, uint32_t start_bit_index)
     230             : {
     231        1726 :         uint32_t bit_index;
     232             : 
     233        1726 :         bit_index = bit_array_find_first(ba, start_bit_index, 0);
     234             : 
     235             :         /*
     236             :          * If we ran off the end of the array and found the 1 bit in the extra word,
     237             :          * return UINT32_MAX to indicate no actual 1 bits were found.
     238             :          */
     239        1726 :         if (bit_index >= ba->bit_count) {
     240         373 :                 bit_index = UINT32_MAX;
     241         373 :         }
     242             : 
     243        3452 :         return bit_index;
     244        1726 : }
     245             : 
     246             : uint32_t
     247       16699 : spdk_bit_array_find_first_clear(const struct spdk_bit_array *ba, uint32_t start_bit_index)
     248             : {
     249       16699 :         uint32_t bit_index;
     250             : 
     251       16699 :         bit_index = bit_array_find_first(ba, start_bit_index, SPDK_BIT_ARRAY_WORD_C(-1));
     252             : 
     253             :         /*
     254             :          * If we ran off the end of the array and found the 0 bit in the extra word,
     255             :          * return UINT32_MAX to indicate no actual 0 bits were found.
     256             :          */
     257       16699 :         if (bit_index >= ba->bit_count) {
     258         512 :                 bit_index = UINT32_MAX;
     259         512 :         }
     260             : 
     261       33398 :         return bit_index;
     262       16699 : }
     263             : 
     264             : uint32_t
     265        1404 : spdk_bit_array_count_set(const struct spdk_bit_array *ba)
     266             : {
     267        1404 :         const spdk_bit_array_word *cur_word = ba->words;
     268        1404 :         uint32_t word_count = bit_array_word_count(ba->bit_count);
     269        1404 :         uint32_t set_count = 0;
     270             : 
     271       13029 :         while (word_count--) {
     272             :                 /*
     273             :                  * No special treatment is needed for the last (potentially partial) word, since
     274             :                  * spdk_bit_array_resize() makes sure the bits past bit_count are cleared.
     275             :                  */
     276       11625 :                 set_count += SPDK_BIT_ARRAY_WORD_POPCNT(*cur_word++);
     277             :         }
     278             : 
     279        2808 :         return set_count;
     280        1404 : }
     281             : 
     282             : uint32_t
     283        1239 : spdk_bit_array_count_clear(const struct spdk_bit_array *ba)
     284             : {
     285        1239 :         return ba->bit_count - spdk_bit_array_count_set(ba);
     286             : }
     287             : 
     288             : void
     289        2825 : spdk_bit_array_store_mask(const struct spdk_bit_array *ba, void *mask)
     290             : {
     291        2825 :         uint32_t size, i;
     292        2825 :         uint32_t num_bits = spdk_bit_array_capacity(ba);
     293             : 
     294        2825 :         size = num_bits / CHAR_BIT;
     295        2825 :         memcpy(mask, ba->words, size);
     296             : 
     297        2890 :         for (i = 0; i < num_bits % CHAR_BIT; i++) {
     298          65 :                 if (spdk_bit_array_get(ba, i + size * CHAR_BIT)) {
     299           6 :                         ((uint8_t *)mask)[size] |= (1U << i);
     300           6 :                 } else {
     301          59 :                         ((uint8_t *)mask)[size] &= ~(1U << i);
     302             :                 }
     303          65 :         }
     304        2825 : }
     305             : 
     306             : void
     307         662 : spdk_bit_array_load_mask(struct spdk_bit_array *ba, const void *mask)
     308             : {
     309         662 :         uint32_t size, i;
     310         662 :         uint32_t num_bits = spdk_bit_array_capacity(ba);
     311             : 
     312         662 :         size = num_bits / CHAR_BIT;
     313         662 :         memcpy(ba->words, mask, size);
     314             : 
     315         667 :         for (i = 0; i < num_bits % CHAR_BIT; i++) {
     316           5 :                 if (((uint8_t *)mask)[size] & (1U << i)) {
     317           1 :                         spdk_bit_array_set(ba, i + size * CHAR_BIT);
     318           1 :                 } else {
     319           4 :                         spdk_bit_array_clear(ba, i + size * CHAR_BIT);
     320             :                 }
     321           5 :         }
     322         662 : }
     323             : 
     324             : void
     325           1 : spdk_bit_array_clear_mask(struct spdk_bit_array *ba)
     326             : {
     327           1 :         uint32_t size, i;
     328           1 :         uint32_t num_bits = spdk_bit_array_capacity(ba);
     329             : 
     330           1 :         size = num_bits / CHAR_BIT;
     331           1 :         memset(ba->words, 0, size);
     332             : 
     333           6 :         for (i = 0; i < num_bits % CHAR_BIT; i++) {
     334           5 :                 spdk_bit_array_clear(ba, i + size * CHAR_BIT);
     335           5 :         }
     336           1 : }
     337             : 
     338             : struct spdk_bit_pool {
     339             :         struct spdk_bit_array   *array;
     340             :         uint32_t                lowest_free_bit;
     341             :         uint32_t                free_count;
     342             : };
     343             : 
     344             : struct spdk_bit_pool *
     345          10 : spdk_bit_pool_create(uint32_t num_bits)
     346             : {
     347          10 :         struct spdk_bit_pool *pool = NULL;
     348          10 :         struct spdk_bit_array *array;
     349             : 
     350          10 :         array = spdk_bit_array_create(num_bits);
     351          10 :         if (array == NULL) {
     352           0 :                 return NULL;
     353             :         }
     354             : 
     355          10 :         pool = calloc(1, sizeof(*pool));
     356          10 :         if (pool == NULL) {
     357           0 :                 spdk_bit_array_free(&array);
     358           0 :                 return NULL;
     359             :         }
     360             : 
     361          10 :         pool->array = array;
     362          10 :         pool->lowest_free_bit = 0;
     363          10 :         pool->free_count = num_bits;
     364             : 
     365          10 :         return pool;
     366          10 : }
     367             : 
     368             : struct spdk_bit_pool *
     369         938 : spdk_bit_pool_create_from_array(struct spdk_bit_array *array)
     370             : {
     371         938 :         struct spdk_bit_pool *pool = NULL;
     372             : 
     373         938 :         pool = calloc(1, sizeof(*pool));
     374         938 :         if (pool == NULL) {
     375           0 :                 return NULL;
     376             :         }
     377             : 
     378         938 :         pool->array = array;
     379         938 :         pool->lowest_free_bit = spdk_bit_array_find_first_clear(array, 0);
     380         938 :         pool->free_count = spdk_bit_array_count_clear(array);
     381             : 
     382         938 :         return pool;
     383         938 : }
     384             : 
     385             : void
     386         993 : spdk_bit_pool_free(struct spdk_bit_pool **ppool)
     387             : {
     388         993 :         struct spdk_bit_pool *pool;
     389             : 
     390         993 :         if (!ppool) {
     391           0 :                 return;
     392             :         }
     393             : 
     394         993 :         pool = *ppool;
     395         993 :         *ppool = NULL;
     396         993 :         if (pool != NULL) {
     397         948 :                 spdk_bit_array_free(&pool->array);
     398         948 :                 free(pool);
     399         948 :         }
     400         993 : }
     401             : 
     402             : int
     403           0 : spdk_bit_pool_resize(struct spdk_bit_pool **ppool, uint32_t num_bits)
     404             : {
     405           0 :         struct spdk_bit_pool *pool;
     406           0 :         int rc;
     407             : 
     408           0 :         assert(ppool != NULL);
     409             : 
     410           0 :         pool = *ppool;
     411           0 :         rc = spdk_bit_array_resize(&pool->array, num_bits);
     412           0 :         if (rc) {
     413           0 :                 return rc;
     414             :         }
     415             : 
     416           0 :         pool->lowest_free_bit = spdk_bit_array_find_first_clear(pool->array, 0);
     417           0 :         pool->free_count = spdk_bit_array_count_clear(pool->array);
     418             : 
     419           0 :         return 0;
     420           0 : }
     421             : 
     422             : uint32_t
     423        3855 : spdk_bit_pool_capacity(const struct spdk_bit_pool *pool)
     424             : {
     425        3855 :         return spdk_bit_array_capacity(pool->array);
     426             : }
     427             : 
     428             : bool
     429       20515 : spdk_bit_pool_is_allocated(const struct spdk_bit_pool *pool, uint32_t bit_index)
     430             : {
     431       20515 :         return spdk_bit_array_get(pool->array, bit_index);
     432             : }
     433             : 
     434             : uint32_t
     435       10283 : spdk_bit_pool_allocate_bit(struct spdk_bit_pool *pool)
     436             : {
     437       10283 :         uint32_t bit_index = pool->lowest_free_bit;
     438             : 
     439       10283 :         if (bit_index == UINT32_MAX) {
     440           0 :                 return UINT32_MAX;
     441             :         }
     442             : 
     443       10283 :         spdk_bit_array_set(pool->array, bit_index);
     444       10283 :         pool->lowest_free_bit = spdk_bit_array_find_first_clear(pool->array, bit_index);
     445       10283 :         pool->free_count--;
     446       10283 :         return bit_index;
     447       10283 : }
     448             : 
     449             : void
     450        2996 : spdk_bit_pool_free_bit(struct spdk_bit_pool *pool, uint32_t bit_index)
     451             : {
     452        2996 :         assert(spdk_bit_array_get(pool->array, bit_index) == true);
     453             : 
     454        2996 :         spdk_bit_array_clear(pool->array, bit_index);
     455        2996 :         if (pool->lowest_free_bit > bit_index) {
     456        1584 :                 pool->lowest_free_bit = bit_index;
     457        1584 :         }
     458        2996 :         pool->free_count++;
     459        2996 : }
     460             : 
     461             : uint32_t
     462           0 : spdk_bit_pool_count_allocated(const struct spdk_bit_pool *pool)
     463             : {
     464           0 :         return spdk_bit_array_capacity(pool->array) - pool->free_count;
     465             : }
     466             : 
     467             : uint32_t
     468          10 : spdk_bit_pool_count_free(const struct spdk_bit_pool *pool)
     469             : {
     470          10 :         return pool->free_count;
     471             : }
     472             : 
     473             : void
     474         824 : spdk_bit_pool_store_mask(const struct spdk_bit_pool *pool, void *mask)
     475             : {
     476         824 :         spdk_bit_array_store_mask(pool->array, mask);
     477         824 : }
     478             : 
     479             : void
     480          10 : spdk_bit_pool_load_mask(struct spdk_bit_pool *pool, const void *mask)
     481             : {
     482          10 :         spdk_bit_array_load_mask(pool->array, mask);
     483          10 :         pool->lowest_free_bit = spdk_bit_array_find_first_clear(pool->array, 0);
     484          10 :         pool->free_count = spdk_bit_array_count_clear(pool->array);
     485          10 : }
     486             : 
     487             : void
     488           0 : spdk_bit_pool_free_all_bits(struct spdk_bit_pool *pool)
     489             : {
     490           0 :         spdk_bit_array_clear_mask(pool->array);
     491           0 :         pool->lowest_free_bit = 0;
     492           0 :         pool->free_count = spdk_bit_array_capacity(pool->array);
     493           0 : }