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 } 279