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