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