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/stdinc.h" 35 36 #include "spdk/bit_array.h" 37 #include "spdk/env.h" 38 39 #include "spdk/likely.h" 40 #include "spdk/util.h" 41 42 typedef uint64_t spdk_bit_array_word; 43 #define SPDK_BIT_ARRAY_WORD_TZCNT(x) (__builtin_ctzll(x)) 44 #define SPDK_BIT_ARRAY_WORD_POPCNT(x) (__builtin_popcountll(x)) 45 #define SPDK_BIT_ARRAY_WORD_C(x) ((spdk_bit_array_word)(x)) 46 #define SPDK_BIT_ARRAY_WORD_BYTES sizeof(spdk_bit_array_word) 47 #define SPDK_BIT_ARRAY_WORD_BITS (SPDK_BIT_ARRAY_WORD_BYTES * 8) 48 #define SPDK_BIT_ARRAY_WORD_INDEX_SHIFT spdk_u32log2(SPDK_BIT_ARRAY_WORD_BITS) 49 #define SPDK_BIT_ARRAY_WORD_INDEX_MASK ((1u << SPDK_BIT_ARRAY_WORD_INDEX_SHIFT) - 1) 50 51 struct spdk_bit_array { 52 uint32_t bit_count; 53 spdk_bit_array_word words[]; 54 }; 55 56 struct spdk_bit_array * 57 spdk_bit_array_create(uint32_t num_bits) 58 { 59 struct spdk_bit_array *ba = NULL; 60 61 spdk_bit_array_resize(&ba, num_bits); 62 63 return ba; 64 } 65 66 void 67 spdk_bit_array_free(struct spdk_bit_array **bap) 68 { 69 struct spdk_bit_array *ba; 70 71 if (!bap) { 72 return; 73 } 74 75 ba = *bap; 76 *bap = NULL; 77 spdk_dma_free(ba); 78 } 79 80 static inline uint32_t 81 spdk_bit_array_word_count(uint32_t num_bits) 82 { 83 return (num_bits + SPDK_BIT_ARRAY_WORD_BITS - 1) >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT; 84 } 85 86 static inline spdk_bit_array_word 87 spdk_bit_array_word_mask(uint32_t num_bits) 88 { 89 assert(num_bits < SPDK_BIT_ARRAY_WORD_BITS); 90 return (SPDK_BIT_ARRAY_WORD_C(1) << num_bits) - 1; 91 } 92 93 int 94 spdk_bit_array_resize(struct spdk_bit_array **bap, uint32_t num_bits) 95 { 96 struct spdk_bit_array *new_ba; 97 uint32_t old_word_count, new_word_count; 98 size_t new_size; 99 100 if (!bap) { 101 return -EINVAL; 102 } 103 104 new_word_count = spdk_bit_array_word_count(num_bits); 105 new_size = offsetof(struct spdk_bit_array, words) + new_word_count * SPDK_BIT_ARRAY_WORD_BYTES; 106 107 /* 108 * Always keep one extra word with a 0 and a 1 past the actual required size so that the 109 * find_first functions can just keep going until they match. 110 */ 111 new_size += SPDK_BIT_ARRAY_WORD_BYTES; 112 113 new_ba = (struct spdk_bit_array *)spdk_dma_realloc(*bap, new_size, 64, NULL); 114 if (!new_ba) { 115 return -ENOMEM; 116 } 117 118 /* 119 * Set up special extra word (see above comment about find_first_clear). 120 * 121 * This is set to 0b10 so that find_first_clear will find a 0 at the very first 122 * bit past the end of the buffer, and find_first_set will find a 1 at the next bit 123 * past that. 124 */ 125 new_ba->words[new_word_count] = 0x2; 126 127 if (*bap == NULL) { 128 old_word_count = 0; 129 new_ba->bit_count = 0; 130 } else { 131 old_word_count = spdk_bit_array_word_count(new_ba->bit_count); 132 } 133 134 if (new_word_count > old_word_count) { 135 /* Zero out new entries */ 136 memset(&new_ba->words[old_word_count], 0, 137 (new_word_count - old_word_count) * SPDK_BIT_ARRAY_WORD_BYTES); 138 } else if (new_word_count == old_word_count && num_bits < new_ba->bit_count) { 139 /* Make sure any existing partial last word is cleared beyond the new num_bits. */ 140 uint32_t last_word_bits; 141 spdk_bit_array_word mask; 142 143 last_word_bits = num_bits & SPDK_BIT_ARRAY_WORD_INDEX_MASK; 144 mask = spdk_bit_array_word_mask(last_word_bits); 145 new_ba->words[old_word_count - 1] &= mask; 146 } 147 148 new_ba->bit_count = num_bits; 149 *bap = new_ba; 150 return 0; 151 } 152 153 uint32_t 154 spdk_bit_array_capacity(const struct spdk_bit_array *ba) 155 { 156 return ba->bit_count; 157 } 158 159 static inline int 160 _spdk_bit_array_get_word(const struct spdk_bit_array *ba, uint32_t bit_index, 161 uint32_t *word_index, uint32_t *word_bit_index) 162 { 163 if (spdk_unlikely(bit_index >= ba->bit_count)) { 164 return -EINVAL; 165 } 166 167 *word_index = bit_index >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT; 168 *word_bit_index = bit_index & SPDK_BIT_ARRAY_WORD_INDEX_MASK; 169 170 return 0; 171 } 172 173 bool 174 spdk_bit_array_get(const struct spdk_bit_array *ba, uint32_t bit_index) 175 { 176 uint32_t word_index, word_bit_index; 177 178 if (_spdk_bit_array_get_word(ba, bit_index, &word_index, &word_bit_index)) { 179 return false; 180 } 181 182 return (ba->words[word_index] >> word_bit_index) & 1U; 183 } 184 185 int 186 spdk_bit_array_set(struct spdk_bit_array *ba, uint32_t bit_index) 187 { 188 uint32_t word_index, word_bit_index; 189 190 if (_spdk_bit_array_get_word(ba, bit_index, &word_index, &word_bit_index)) { 191 return -EINVAL; 192 } 193 194 ba->words[word_index] |= (SPDK_BIT_ARRAY_WORD_C(1) << word_bit_index); 195 return 0; 196 } 197 198 void 199 spdk_bit_array_clear(struct spdk_bit_array *ba, uint32_t bit_index) 200 { 201 uint32_t word_index, word_bit_index; 202 203 if (_spdk_bit_array_get_word(ba, bit_index, &word_index, &word_bit_index)) { 204 /* 205 * Clearing past the end of the bit array is a no-op, since bit past the end 206 * are implicitly 0. 207 */ 208 return; 209 } 210 211 ba->words[word_index] &= ~(SPDK_BIT_ARRAY_WORD_C(1) << word_bit_index); 212 } 213 214 static inline uint32_t 215 _spdk_bit_array_find_first(const struct spdk_bit_array *ba, uint32_t start_bit_index, 216 spdk_bit_array_word xor_mask) 217 { 218 uint32_t word_index, first_word_bit_index; 219 spdk_bit_array_word word, first_word_mask; 220 const spdk_bit_array_word *words, *cur_word; 221 222 if (spdk_unlikely(start_bit_index >= ba->bit_count)) { 223 return ba->bit_count; 224 } 225 226 word_index = start_bit_index >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT; 227 words = ba->words; 228 cur_word = &words[word_index]; 229 230 /* 231 * Special case for first word: skip start_bit_index % SPDK_BIT_ARRAY_WORD_BITS bits 232 * within the first word. 233 */ 234 first_word_bit_index = start_bit_index & SPDK_BIT_ARRAY_WORD_INDEX_MASK; 235 first_word_mask = spdk_bit_array_word_mask(first_word_bit_index); 236 237 word = (*cur_word ^ xor_mask) & ~first_word_mask; 238 239 /* 240 * spdk_bit_array_resize() guarantees that an extra word with a 1 and a 0 will always be 241 * at the end of the words[] array, so just keep going until a word matches. 242 */ 243 while (word == 0) { 244 word = *++cur_word ^ xor_mask; 245 } 246 247 return ((uintptr_t)cur_word - (uintptr_t)words) * 8 + SPDK_BIT_ARRAY_WORD_TZCNT(word); 248 } 249 250 251 uint32_t 252 spdk_bit_array_find_first_set(const struct spdk_bit_array *ba, uint32_t start_bit_index) 253 { 254 uint32_t bit_index; 255 256 bit_index = _spdk_bit_array_find_first(ba, start_bit_index, 0); 257 258 /* 259 * If we ran off the end of the array and found the 1 bit in the extra word, 260 * return UINT32_MAX to indicate no actual 1 bits were found. 261 */ 262 if (bit_index >= ba->bit_count) { 263 bit_index = UINT32_MAX; 264 } 265 266 return bit_index; 267 } 268 269 uint32_t 270 spdk_bit_array_find_first_clear(const struct spdk_bit_array *ba, uint32_t start_bit_index) 271 { 272 return _spdk_bit_array_find_first(ba, start_bit_index, SPDK_BIT_ARRAY_WORD_C(-1)); 273 } 274 275 uint32_t 276 spdk_bit_array_count_set(const struct spdk_bit_array *ba) 277 { 278 const spdk_bit_array_word *cur_word = ba->words; 279 uint32_t word_count = spdk_bit_array_word_count(ba->bit_count); 280 uint32_t set_count = 0; 281 282 while (word_count--) { 283 /* 284 * No special treatment is needed for the last (potentially partial) word, since 285 * spdk_bit_array_resize() makes sure the bits past bit_count are cleared. 286 */ 287 set_count += SPDK_BIT_ARRAY_WORD_POPCNT(*cur_word++); 288 } 289 290 return set_count; 291 } 292 293 uint32_t 294 spdk_bit_array_count_clear(const struct spdk_bit_array *ba) 295 { 296 return ba->bit_count - spdk_bit_array_count_set(ba); 297 } 298