ceph/src/spdk/lib/util/bit_array.c

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright (c) Intel Corporation.
   5  *   All rights reserved.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following conditions
   9  *   are met:
  10  *
  11  *     * Redistributions of source code must retain the above copyright
  12  *       notice, this list of conditions and the following disclaimer.
  13  *     * Redistributions in binary form must reproduce the above copyright
  14  *       notice, this list of conditions and the following disclaimer in
  15  *       the documentation and/or other materials provided with the
  16  *       distribution.
  17  *     * Neither the name of Intel Corporation nor the names of its
  18  *       contributors may be used to endorse or promote products derived
  19  *       from this software without specific prior written permission.
  20  *
  21  *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  24  *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  25  *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  26  *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  27  *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  31  *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 #include "spdk/bit_array.h"
  35 #include "spdk/env.h"
  36
  37 #include <assert.h>
  38 #include <errno.h>
  39 #include <limits.h>
  40 #include <stdbool.h>
  41 #include <stddef.h>
  42 #include <stdlib.h>
  43 #include <string.h>
  44
  45 #include "spdk/likely.h"
  46 #include "spdk/util.h"
  47
  48 typedef uint64_t spdk_bit_array_word;
  49 #define SPDK_BIT_ARRAY_WORD_TZCNT(x)    (__builtin_ctzll(x))
  50 #define SPDK_BIT_ARRAY_WORD_C(x)        ((spdk_bit_array_word)(x))
  51 #define SPDK_BIT_ARRAY_WORD_BYTES       sizeof(spdk_bit_array_word)
  52 #define SPDK_BIT_ARRAY_WORD_BITS        (SPDK_BIT_ARRAY_WORD_BYTES * 8)
  53 #define SPDK_BIT_ARRAY_WORD_INDEX_SHIFT spdk_u32log2(SPDK_BIT_ARRAY_WORD_BITS)
  54 #define SPDK_BIT_ARRAY_WORD_INDEX_MASK  ((1u << SPDK_BIT_ARRAY_WORD_INDEX_SHIFT) - 1)
  55
  56 struct spdk_bit_array {
  57         uint32_t bit_count;
  58         spdk_bit_array_word words[];
  59 };
  60
  61 struct spdk_bit_array *
  62 spdk_bit_array_create(uint32_t num_bits)
  63 {
  64         struct spdk_bit_array *ba = NULL;
  65
  66         spdk_bit_array_resize(&ba, num_bits);
  67
  68         return ba;
  69 }
  70
  71 void
  72 spdk_bit_array_free(struct spdk_bit_array **bap)
  73 {
  74         struct spdk_bit_array *ba;
  75
  76         if (!bap) {
  77                 return;
  78         }
  79
  80         ba = *bap;
  81         *bap = NULL;
  82         spdk_free(ba);
  83 }
  84
  85 static inline uint32_t
  86 spdk_bit_array_word_count(uint32_t num_bits)
  87 {
  88         return (num_bits + SPDK_BIT_ARRAY_WORD_BITS - 1) >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT;
  89 }
  90
  91 static inline spdk_bit_array_word
  92 spdk_bit_array_word_mask(uint32_t num_bits)
  93 {
  94         assert(num_bits < SPDK_BIT_ARRAY_WORD_BITS);
  95         return (SPDK_BIT_ARRAY_WORD_C(1) << num_bits) - 1;
  96 }
  97
  98 int
  99 spdk_bit_array_resize(struct spdk_bit_array **bap, uint32_t num_bits)
 100 {
 101         struct spdk_bit_array *new_ba;
 102         uint32_t old_word_count, new_word_count;
 103         size_t new_size;
 104
 105         if (!bap) {
 106                 return -EINVAL;
 107         }
 108
 109         new_word_count = spdk_bit_array_word_count(num_bits);
 110         new_size = offsetof(struct spdk_bit_array, words) + new_word_count * SPDK_BIT_ARRAY_WORD_BYTES;
 111
 112         /*
 113          * Always keep one extra word with a 0 and a 1 past the actual required size so that the
 114          * find_first functions can just keep going until they match.
 115          */
 116         new_size += SPDK_BIT_ARRAY_WORD_BYTES;
 117
 118         new_ba = (struct spdk_bit_array *)spdk_realloc(*bap, new_size, 64, NULL);
 119         if (!new_ba) {
 120                 return -ENOMEM;
 121         }
 122
 123         /*
 124          * Set up special extra word (see above comment about find_first_clear).
 125          *
 126          * This is set to 0b10 so that find_first_clear will find a 0 at the very first
 127          * bit past the end of the buffer, and find_first_set will find a 1 at the next bit
 128          * past that.
 129          */
 130         new_ba->words[new_word_count] = 0x2;
 131
 132         if (*bap == NULL) {
 133                 old_word_count = 0;
 134                 new_ba->bit_count = 0;
 135         } else {
 136                 old_word_count = spdk_bit_array_word_count(new_ba->bit_count);
 137         }
 138
 139         if (new_word_count > old_word_count) {
 140                 /* Zero out new entries */
 141                 memset(&new_ba->words[old_word_count], 0,
 142                        (new_word_count - old_word_count) * SPDK_BIT_ARRAY_WORD_BYTES);
 143         } else if (new_word_count == old_word_count && num_bits < new_ba->bit_count) {
 144                 /* Make sure any existing partial last word is cleared beyond the new num_bits. */
 145                 uint32_t last_word_bits;
 146                 spdk_bit_array_word mask;
 147
 148                 last_word_bits = num_bits & SPDK_BIT_ARRAY_WORD_INDEX_MASK;
 149                 mask = spdk_bit_array_word_mask(last_word_bits);
 150                 new_ba->words[old_word_count - 1] &= mask;
 151         }
 152
 153         new_ba->bit_count = num_bits;
 154         *bap = new_ba;
 155         return 0;
 156 }
 157
 158 uint32_t
 159 spdk_bit_array_capacity(const struct spdk_bit_array *ba)
 160 {
 161         return ba->bit_count;
 162 }
 163
 164 static inline int
 165 _spdk_bit_array_get_word(const struct spdk_bit_array *ba, uint32_t bit_index,
 166                          uint32_t *word_index, uint32_t *word_bit_index)
 167 {
 168         if (spdk_unlikely(bit_index >= ba->bit_count)) {
 169                 return -EINVAL;
 170         }
 171
 172         *word_index = bit_index >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT;
 173         *word_bit_index = bit_index & SPDK_BIT_ARRAY_WORD_INDEX_MASK;
 174
 175         return 0;
 176 }
 177
 178 bool
 179 spdk_bit_array_get(const struct spdk_bit_array *ba, uint32_t bit_index)
 180 {
 181         uint32_t word_index, word_bit_index;
 182
 183         if (_spdk_bit_array_get_word(ba, bit_index, &word_index, &word_bit_index)) {
 184                 return false;
 185         }
 186
 187         return (ba->words[word_index] >> word_bit_index) & 1U;
 188 }
 189
 190 int
 191 spdk_bit_array_set(struct spdk_bit_array *ba, uint32_t bit_index)
 192 {
 193         uint32_t word_index, word_bit_index;
 194
 195         if (_spdk_bit_array_get_word(ba, bit_index, &word_index, &word_bit_index)) {
 196                 return -EINVAL;
 197         }
 198
 199         ba->words[word_index] |= (SPDK_BIT_ARRAY_WORD_C(1) << word_bit_index);
 200         return 0;
 201 }
 202
 203 void
 204 spdk_bit_array_clear(struct spdk_bit_array *ba, uint32_t bit_index)
 205 {
 206         uint32_t word_index, word_bit_index;
 207
 208         if (_spdk_bit_array_get_word(ba, bit_index, &word_index, &word_bit_index)) {
 209                 /*
 210                  * Clearing past the end of the bit array is a no-op, since bit past the end
 211                  * are implicitly 0.
 212                  */
 213                 return;
 214         }
 215
 216         ba->words[word_index] &= ~(SPDK_BIT_ARRAY_WORD_C(1) << word_bit_index);
 217 }
 218
 219 static inline uint32_t
 220 _spdk_bit_array_find_first(const struct spdk_bit_array *ba, uint32_t start_bit_index,
 221                            spdk_bit_array_word xor_mask)
 222 {
 223         uint32_t word_index, first_word_bit_index;
 224         spdk_bit_array_word word, first_word_mask;
 225         const spdk_bit_array_word *words, *cur_word;
 226
 227         if (spdk_unlikely(start_bit_index >= ba->bit_count)) {
 228                 return ba->bit_count;
 229         }
 230
 231         word_index = start_bit_index >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT;
 232         words = ba->words;
 233         cur_word = &words[word_index];
 234
 235         /*
 236          * Special case for first word: skip start_bit_index % SPDK_BIT_ARRAY_WORD_BITS bits
 237          * within the first word.
 238          */
 239         first_word_bit_index = start_bit_index & SPDK_BIT_ARRAY_WORD_INDEX_MASK;
 240         first_word_mask = spdk_bit_array_word_mask(first_word_bit_index);
 241
 242         word = (*cur_word ^ xor_mask) & ~first_word_mask;
 243
 244         /*
 245          * spdk_bit_array_resize() guarantees that an extra word with a 1 and a 0 will always be
 246          * at the end of the words[] array, so just keep going until a word matches.
 247          */
 248         while (word == 0) {
 249                 word = *++cur_word ^ xor_mask;
 250         }
 251
 252         return ((uintptr_t)cur_word - (uintptr_t)words) * 8 + SPDK_BIT_ARRAY_WORD_TZCNT(word);
 253 }
 254
 255
 256 uint32_t
 257 spdk_bit_array_find_first_set(const struct spdk_bit_array *ba, uint32_t start_bit_index)
 258 {
 259         uint32_t bit_index;
 260
 261         bit_index = _spdk_bit_array_find_first(ba, start_bit_index, 0);
 262
 263         /*
 264          * If we ran off the end of the array and found the 1 bit in the extra word,
 265          * return UINT32_MAX to indicate no actual 1 bits were found.
 266          */
 267         if (bit_index >= ba->bit_count) {
 268                 bit_index = UINT32_MAX;
 269         }
 270
 271         return bit_index;
 272 }
 273
 274 uint32_t
 275 spdk_bit_array_find_first_clear(const struct spdk_bit_array *ba, uint32_t start_bit_index)
 276 {
 277         return _spdk_bit_array_find_first(ba, start_bit_index, SPDK_BIT_ARRAY_WORD_C(-1));
 278 }